【算法篇】动态规划类（4）——子序列（笔记）

目录

一、Leetcode 题目 

1. 最长递增子序列

2. 最长连续递增序列

3. 最长重复子数组

4. 最长公共子序列

5. 不相交的线

6. 最大子序和

7. 判断子序列

8. 不同的子序列

9. 两个字符串的删除操作

10. 编辑距离

11. 回文子串

12. 最长回文子序列

二、动态规划总结

一、Leetcode 题目 

1. 最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-increasing-subsequence/description/

        给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

        子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

思路：

    ① dp[i] 表示 i 之前包括i的以 nums[i] 结尾的最长递增子序列的长度

    ② 位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。

所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

    ③ 每一个 i，对应的 dp[i]（即最长递增子序列）起始大小至少都是 1.

    ④ dp[i] 是有 0 到 i-1 各个位置的最长递增子序列 推导而来，那么遍历 i 一定是从前向后遍历。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取长的子序列}return result;}
};

2. 最长连续递增序列

https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

        给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

        连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

思路：

    ① dp[i]：以下标i为结尾的连续递增的子序列长度为 dp[i]。

    ② 如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以 i - 1 为结尾的连续递增的子序列长度 + 1 。

即：dp[i] = dp[i - 1] + 1;

    ③ 以下标 i 为结尾的连续递增的子序列长度最少也应该是 1，即就是 nums[i] 这一个元素。所以 dp[i] 应该初始 1;

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};

3. 最长重复子数组

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

        给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

思路：

    ① dp[i][j] ：以下标 i - 1 为结尾的 A，和以下标 j - 1 为结尾的 B，最长重复子数组长度为 dp[i][j]。 （特别注意： “以下标 i - 1 为结尾的 A” 标明一定是 以 A[i-1] 为结尾的字符串 ）

    ② 根据 dp[i][j] 的定义，dp[i][j] 的状态只能由 dp[i - 1][j - 1] 推导出来。即当 A[i - 1] 和  B[j - 1] 相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;

    ③ 为了方便递归公式 dp[i][j] = dp[i - 1][j - 1] + 1，所以 dp[i][0] 和 dp[0][j] 初始化为 0。

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size();int len2 = nums2.size();vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));int result = 0;for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}if (dp[i][j] > result) result = dp[i][j];}}return result;}
};

4. 最长公共子序列

https://leetcode.cn/problems/longest-common-subsequence/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-common-subsequence/description/

        给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

        一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

思路：

    ① dp[i][j]：长度为 [0, i - 1] 的字符串 text1 与长度为 [0, j - 1] 的字符串 text2 的最长公共子序列为 dp[i][j]

    ② 主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1] 不相同。

  • 如果 text1[i - 1] 与 text2[j - 1] 相同，那么找到了一个公共元素，所以 dp[i][j] = dp[i - 1][j - 1] + 1;
  • 如果 text1[i - 1] 与 text2[j - 1] 不相同，那就看看 text1[0, i - 2] 与 text2[0, j - 1] 的最长公共子序列 和 text1[0, i - 1] 与 text2[0, j - 2] 的最长公共子序列，取最大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    ③ test1[0, i-1] 和空串的最长公共子序列自然是 0，所以 dp[i][0] = 0。同理 dp[0][j] 也是0。

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 另两个公共子序列有可能是}}}return dp[text1.size()][text2.size()];}
};

5. 不相交的线

https://leetcode.cn/problems/uncrossed-lines/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/uncrossed-lines/description/

        在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

        现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

  •  nums1[i] == nums2[j]
  • 且绘制的直线不与任何其他连线（非水平线）相交。

        请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

        以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

思路：

        本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {if (!nums1.size() || !nums2.size()) return 0;vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[nums1.size()][nums2.size()];}
};

6. 最大子序和

https://leetcode.cn/problems/maximum-subarray/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/maximum-subarray/description/

        给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

        子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1]
输出：1示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

思路：

    ① dp[i]：包括下标 i（以 nums[i] 为结尾）的最大连续子序列和为 dp[i]。

    ② dp[i] 只有两个方向可以推出来：

  • dp[i - 1] + nums[i]，即：nums[i] 加入当前连续子序列和
  • nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以 dp[i] = max(dp[i - 1] + nums[i], nums[i]);

    ③ dp[0] 应为 nums[0] 即 dp[0] = nums[0]。

// 写法一：
class Solution {
public:int maxSubArray(vector<int>& nums) {if (nums.size() == 0) return 0;vector<int> dp(nums.size());dp[0] = nums[0];int result = nums[0];for (int i = 1; i < nums.size(); i++) {// 有两种情况// 第一种：延续之前的累加；第二种：从当前数字进行累加。dp[i] = max(dp[i - 1] + nums[i], nums[i]);if (dp[i] > result) result = dp[i];}return result;}
};// 写法二：
class Solution {
public:int maxSubArray(vector<int>& nums) {if (nums.size() == 0) return 0;int result = INT_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) {count += nums[i];result = result > count ? result : count;if (count < 0) count = 0;}return result;}
};

7. 判断子序列

https://leetcode.cn/problems/is-subsequence/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/is-subsequence/description/

        给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

        字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

        如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false

思路：

    ① dp[i][j] 表示以下标 i-1 为结尾的字符串 s，和以下标 j-1 为结尾的字符串 t，相同子序列的长度为 dp[i][j]。

    ② 首先要考虑如下两种操作：

  • if (s[i - 1] == t[j - 1])
    • t 中找到了一个字符在 s 中也出现了
  • if (s[i - 1] != t[j - 1])
    • 相当于 t 要删除元素，继续匹配

        if (s[i - 1] == t[j - 1])，那么 dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在 dp[i-1][j-1] 的基础上加 1。

        if (s[i - 1] != t[j - 1])，此时相当于 t 要删除元素，t 如果把当前元素 t[j - 1] 删除，那么dp[i][j] 的数值就是 看 s[i - 1] 与 t[j - 2] 的比较结果了，即：dp[i][j] = dp[i][j - 1];

    ③ 从递推公式可以看出 dp[i][j] 都是依赖于 dp[i - 1][j - 1] 和 dp[i][j - 1]，所以 dp[0][0] 和 dp[i][0] 是一定要初始化的。dp[i][0] 表示以下标 i-1 为结尾的字符串，与空字符串的相同子序列长度，所以为 0. dp[0][j] 同理。

class Solution {
public:bool isSubsequence(string s, string t) {if (s.size() == 0) return true;vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = dp[i][j - 1];}}if (dp[s.size()][t.size()] == s.size()) return true;return false;}
};

8. 不同的子序列

https://leetcode.cn/problems/distinct-subsequences/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/distinct-subsequences/description/

        给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3示例 2：
输入：s = "babgbag", t = "bag"
输出：5

思路：

    ① dp[i][j]：以 i-1 为结尾的 s 子序列中出现以 j-1 为结尾的t的个数为 dp[i][j]。

    ② 要分析两种情况

  • s[i - 1] 与 t[j - 1]相等
  • s[i - 1] 与 t[j - 1] 不相等

        当 s[i - 1] 与 t[j - 1] 相等时，dp[i][j] 可以有两部分组成。

        一部分是用 s[i - 1] 来匹配，那么个数为 dp[i - 1][j - 1]。即不需要考虑当前 s 子串和 t 子串的最后一位字母，所以只需要 dp[i-1][j-1]。

        一部分是不用 s[i - 1] 来匹配，个数为 dp[i - 1][j]。

        所以，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

        当 s[i - 1] 与 t[j - 1] 不相等时，dp[i][j] 只有一部分组成，不用 s[i - 1] 来匹配（就是模拟在 s 中删除这个元素），即：dp[i - 1][j]

        所以递推公式为：dp[i][j] = dp[i - 1][j];

    ③ dp[i][0] 表示：以 i-1 为结尾的 s 可以随便删除元素，出现空字符串的个数。

        那么 dp[i][0] 一定都是 1，因为也就是把以 i-1 为结尾的 s，删除所有元素，出现空字符串的个数就是 1。

        再来看 dp[0][j]，dp[0][j]：空字符串 s 可以随便删除元素，出现以 j-1 为结尾的字符串 t 的个数。

        那么 dp[0][j] 一定都是 0，s 如论如何也变成不了 t。

        dp[0][0] 应该是 1，空字符串s，可以删除 0 个元素，变成空字符串 t。

class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(t.size() + 1, vector<uint64_t>(s.size() + 1, 0));// 初始化for (int i = 0; i <= s.size(); i++) dp[0][i] = 1;for (int i = 1; i <= t.size(); i++) {for (int j = 1; j <= s.size(); j++) {if (t[i - 1] == s[j - 1]) {// 考虑s当前字符，；不考虑当前字符dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];}else {dp[i][j] = dp[i][j - 1];}}}return dp[t.size()][s.size()];}
};

9. 两个字符串的删除操作

https://leetcode.cn/problems/delete-operation-for-two-strings/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/delete-operation-for-two-strings/description/

        给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。每步 可以删除任意一个字符串中的一个字符。

示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"示例  2:
输入：word1 = "leetcode", word2 = "etco"
输出：4

思路：

    ① dp[i][j]：以 i-1 为结尾的字符串 word1，和以 j-1 位结尾的字符串 word2，想要达到相等，所需要删除元素的最少次数。

    ② 当 word1[i - 1] 与 word2[j - 1] 相同的时候，dp[i][j] = dp[i - 1][j - 1]；当 word1[i - 1] 与 word2[j - 1] 不相同的时候，有三种情况：

  • 情况一：删 word1[i - 1]，最少操作次数为 dp[i - 1][j] + 1
  • 情况二：删 word2[j - 1]，最少操作次数为 dp[i][j - 1] + 1
  • 情况三：同时删 word1[i - 1] 和 word2[j - 1]，操作的最少次数为 dp[i - 1][j - 1] + 2

        那最后当然是取最小值，所以当 word1[i - 1] 与 word2[j - 1] 不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

        因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

    ③ 从递推公式中，可以看出来，dp[i][0] 和 dp[0][j] 是一定要初始化的。

        dp[i][0]：word2 为空字符串，以 i-1 为结尾的字符串 word1 要删除多少个元素，才能和 word2 相同呢，很明显 dp[i][0] = i。

class Solution {
public:int minDistance(string word1, string word2) {int len1 = word1.size();int len2 = word2.size();if (len1 == 0) return len2;else if (len2 == 0) return len1;vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return (len1 + len2 - 2 * dp[len1][len2]);}
};

10. 编辑距离

https://leetcode.cn/problems/edit-distance/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/edit-distance/description/

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

思路：

        dp[i][j] 表示以下标 i-1 为结尾的字符串 word1，和以下标 j-1 为结尾的字符串 word2，最近编辑距离为 dp[i][j]。

class Solution {
public:int minDistance(string word1, string word2) {int len1 = word1.size();int len2 = word2.size();if (len1 == 0) return len2;else if (len2 == 0) return len1;// dp 表示为以 i-1 为结尾的字符串转换为以 j-1 为结尾的字符串的最小步数vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));for (int i = 1; i <= len1; i++) dp[i][0] = i;for (int j = 1; j <= len2; j++) dp[0][j] = j;for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];    // 两字符相同，最小步数与以 i-2 和 j-2 的字符相同}else {// 三种情况// 第一种：dp[i - 1][j - 1] 表示为替换// 第二/三种：dp[i - 1][j]、dp[i][j - 1] 表示为删除其中一个字符串的字符dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;}}}return dp[len1][len2];}
};

11. 回文子串

https://leetcode.cn/problems/palindromic-substrings/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/palindromic-substrings/description/

        给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

思路：

    ① 布尔类型的 dp[i][j]：表示区间范围 [i, j] （注意是左闭右闭）的子串是否是回文子串，如果是 dp[i][j] 为 true，否则为 false。

    ② 当 s[i] 与 s[j] 不相等，dp[i][j] 一定是 false。当 s[i] 与 s[j] 相等时，这就复杂一些了，有如下三种情况：

  • 情况一：下标 i 与 j 相同，同一个字符例如 a，当然是回文子串
  • 情况二：下标 i 与 j 相差为 1，例如 aa，也是回文子串
  • 情况三：下标：i 与 j 相差大于 1 的时候，例如 cabac，此时 s[i] 与 s[j] 已经相同了，我们看 i 到 j 区间是不是回文子串就看 aba 是不是回文就可以了，那么 aba 的区间就是 i+1 与 j-1 区间，这个区间是不是回文就看 dp[i + 1][j - 1] 是否为 true。

    ③ dp[i][j] 初始化为 false。

// 写法一：
class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) {dp[i][j] = true;result++;}else if (dp[i + 1][j - 1]) {dp[i][j] = true;result++;}}}}return result;}
};// 写法二：（改进）
class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j < s.size(); j++) {if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {result++;dp[i][j] = true;}}}return result;}
};

 

12. 最长回文子序列

https://leetcode.cn/problems/longest-palindromic-subsequence/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-palindromic-subsequence/description/

        给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

        子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

思路：

    ① dp[i][j]：字符串 s 在 [i, j] 范围内最长的回文子序列的长度为 dp[i][j]。

    ② 关键逻辑就是看 s[i] 与 s[j] 是否相同。

如果 s[i] 与 s[j] 相同，那么 dp[i][j] = dp[i + 1][j - 1] + 2;

        如果 s[i] 与 s[j] 不相同，说明 s[i] 和 s[j] 的同时加入 并不能增加 [i, j] 区间回文子序列的长度，那么分别加入 s[i]、s[j] 看看哪一个可以组成最长的回文子序列。

        加入 s[j] 的回文子序列长度为 dp[i + 1][j]。

        加入s[i]  的回文子序列长度为 dp[i][j - 1]。

那么 dp[i][j] 一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));for (int i = 0; i < s.size(); i++) dp[i][i] = 1;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); j++) {if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;}else {dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][s.size() - 1];}
};

二、动态规划总结

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/455831.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

ctfshow-web入门-web31

ctfshow-web入门-web31

<?php ​ /* # -*- coding: utf-8 -*- # Author: h1xa # Date: 2020-09-04 00:12:34 # Last Modified by: h1xa # Last Modified time: 2020-09-04 00:49:10 # email: h1xactfer.com # link: https://ctfer.com ​ */ ​ error_reporting(0); if(isset($_GET[c])){$c …
阅读更多...
Java语言-接口（下）

Java语言-接口（下）

目录 1. 接口使用实例 1.1 给对象数组排序 1.2 Clonable接口和深拷贝 Cloneable 浅拷贝 深拷贝 1.3 抽象类和接口的区别 2. Object类 2.1 Object类的介绍 2.2 toString() 2.3 equals() 2.4 hashcode() 1. 接口使用实例 1.1 给对象数组排序 现有一个学生类&#…
阅读更多...
关于java继承（深入解析父类属性的抽取与构造函数的作用）

关于java继承（深入解析父类属性的抽取与构造函数的作用）

目录 前言基础继承作用 理论分析父类属性的抽取构造函数调用父类构造函数会不会创建一个父类的对象&#xff1f;生命周期角度谁的属性用谁的构造函数初始化 示例解析代码代码调试展示构造函数初始化成员变量 总结 前言 在Java中&#xff0c;继承是一项至关重要的特性&#xff0…
阅读更多...
详解23种设计模式——第二部分：结构型模式

详解23种设计模式——第二部分：结构型模式

目录 3 结构型模式 3.1 代理模式 3.2 适配器模式 3.2.1 默认适配器模式 3.2.2 对象适配器模式 3.2.3 类适配器模式 3.2.4 适配器模式总结 3.3 桥梁模式 3.4 装饰模式 3.4 门面模式 3.5 组合模式 3.6 享元模式 3.7 结构型模式总结 接上一篇&#xff1a;详解23种设计…
阅读更多...
openrtp 音视频时间戳问题

openrtp 音视频时间戳问题

解决音视频发送的rtp问题 openrtp增加了音频aac的发送&#xff0c;地址 OpenRTP Gitee开源地址 同时使用两个rtp &#xff0c;来发送音频和视频 使用以下音频rtp&#xff0c;是可以发送和接收的&#xff0c;音频端口在视频端口上2 v0 o- 0 0 IN IP4 127.0.0.1 sMy Stream cI…
阅读更多...
Windows通过netsh控制安全中心防火墙和网络保护策略

Windows通过netsh控制安全中心防火墙和网络保护策略

Windows通过netsh控制安全中心防火墙和网络保护策略 1. 工具简介 【1】. Windows安全中心 【2】. netsh工具 netsh(Network Shell) 是一个Windows系统本身提供的功能强大的网络配置命令行工具。 2. 开启/关闭防火墙策略 在设置端口&#xff08;禁用/启用&#xff09;前&am…
阅读更多...
使用 CDN 后 Apache 的日志记录客户真实 IP

使用 CDN 后 Apache 的日志记录客户真实 IP

经常搭建网站服务器的都知道&#xff0c;在给站点使用了 CDN 后 Web 应用的日志记录里就会只记录 CDN 节点 IP 了&#xff0c;这就没法看到真实客户请求 IP&#xff0c;对于日志分析、运维日常维护来说就有点儿麻烦了&#xff0c;今天明月结合在五洛云服务器上搭建的Apache环境…
阅读更多...
多ip访问多网站

多ip访问多网站

多IP访问多网站 1.预配操作 [rootlocalhost ~]# mount /dev/sr0 /mnt mount: /mnt: WARNING: source write-protected, mounted read-only. [rootlocalhost ~]# systemctl stop firewalld ----------关闭防火墙 [rootlocalhost ~]# setenforce 0 -------关闭selinux2.安装n…
阅读更多...
【论文阅读】ESRGAN

【论文阅读】ESRGAN

学习资料 论文题目：增强型超分辨率生成对抗网络（ESRGAN: Enhanced Super-Resolution Generative Adversarial Networks）论文地址：[1809.00219] ESRGAN：增强型超分辨率生成对抗网络代码：xinntao / ESRGAN：ECCV18 研讨会 - 增强的 SRGAN。Champion PIRM Challenge 关于感知…
阅读更多...
【机器学习】VQ-VAE（Vector Quantized Variational Autoencoder）

【机器学习】VQ-VAE（Vector Quantized Variational Autoencoder）

VQ-VAE&#xff08;Vector Quantized Variational Autoencoder&#xff09;是一种生成模型&#xff0c;它结合了变分自编码器&#xff08;Variational Autoencoder, VAE&#xff09;和向量量化&#xff08;Vector Quantization&#xff09;技术。VQ-VAE的主要目的在于通过离散潜…
阅读更多...
【动态规划】子序列问题（上）

【动态规划】子序列问题（上）

1. 最长递增子序列 300. 最长递增子序列 和子数组不同的是&#xff0c;子数组要求是连续的&#xff0c;子序列只要下标是递增的就可以&#xff0c;这里严格递增的意思是不能有相等的元素&#xff0c;必须一直递增 状态表示&#xff1a;以 i 位置为结尾的所有的子序列中最长递…
阅读更多...
Android GPU Inspector分析帧数据快速入门

Android GPU Inspector分析帧数据快速入门

使用 谷歌官方工具Android GPU Inspector (AGI) 可以对Android 应用进行深入和全面的系统性能分析和帧性能分析 。AGI 是一个非常强大的分析工具&#xff0c;尤其是在需要诊断 GPU 性能问题和优化应用时&#xff0c;可以帮助你精准找到性能瓶颈。本文介绍如何使用该工具对帧数据…
阅读更多...
梳理一下spring中，与message相关的知识点

梳理一下spring中，与message相关的知识点

本次梳理的相关知识点包括jms&#xff0c;amqp(rabbitmq)&#xff0c;sping-messaging&#xff0c;spring-integration&#xff0c;springcloud-stream&#xff0c;这些都是与消息message相关的内容&#xff0c;它们有什么区别与联系呢&#xff1f; 相关的要点与相互关系都整理…
阅读更多...
物联网消息队列Emqx日志配置及日志追踪以及Centos7上的rc.local开机不执行、git提交的小问题

物联网消息队列Emqx日志配置及日志追踪以及Centos7上的rc.local开机不执行、git提交的小问题

一、物联网消息队列Emqx日志配置及日志追踪 EMQX支持将日志输出到控制台或者日志文件&#xff0c;或者同时使用两者。使用 Docker 部署 EMQX&#xff0c;默认只能通过 docker logs 命令查看 EMQX 日志。EMQX 的默认日志级别为 warning&#xff0c;默认在单日志文件超过10MB(log…
阅读更多...
word压缩大小怎么弄？快来试试这几种压缩word方法！

word压缩大小怎么弄？快来试试这几种压缩word方法！

word压缩大小怎么弄&#xff1f;在处理Word文档时&#xff0c;如果遇到体积过大的情况&#xff0c;无疑会带来一系列麻烦&#xff0c;大型Word文档不仅占据大量存储空间&#xff0c;而且在传输过程中会耗费更多时间&#xff0c;想象一下&#xff0c;当你急需将一份重要的文档发…
阅读更多...
Perl打印9x9乘法口诀

Perl打印9x9乘法口诀

本章教程主要介绍如何用Perl打印9x9乘法口诀。 一、程序代码 1、写法① use strict; # 启用严格模式&#xff0c;帮助捕捉变量声明等错误 use warnings; # 启用警告&#xff0c;帮助发现潜在问题# 遍历 1 到 9 的数字 for my $i (1..9) {# 对于每个 $i&#xff0c;遍历 1…
阅读更多...
【设计模式系列】观察者模式

【设计模式系列】观察者模式

一、什么是观察者模式 观察者模式&#xff08;Observer Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了对象之间的一对多依赖关系&#xff0c;当一个对象的状态发生变化时&#xff0c;所有依赖于它的对象都会得到通知并自动更新。这种模式也被称为发布-订阅模式&…
阅读更多...
【AscendC算子开发】笔记2 算子高级开发和调试调优

【AscendC算子开发】笔记2 算子高级开发和调试调优

算子调试 Tensor也可以通过特定的printf方法来打印&#xff0c;见上图。 gdb调试见上图。 为什么gdb调试无法成功&#xff0c;因为run.sh里面有两行export&#xff0c;如果直接通过.XX运行的话需要配置一下。 npu域也支持调试&#xff0c;可以使用上述的方法。 内存检测工…
阅读更多...
AI自动生成PPT哪个软件好？智能生成PPT不再熬夜做课件

AI自动生成PPT哪个软件好？智能生成PPT不再熬夜做课件

大概这世上&#xff0c;都是职场牛马对“PPT”这三个字母的头痛反应最大吧&#xff01; 是的&#xff0c;就连各个年级段的老师也是很头痛——愁着怎样能在排版整齐的情况下&#xff0c;将必考知识点都呈现在PPT每一张幻灯片页面里...... 近期打听到用人工智能生成ppt课件&am…
阅读更多...
ProtoBuf 的含义和安装

ProtoBuf 的含义和安装

ProtoBuf 是什么 Protocol Buffers 是 Google 的⼀种语⾔⽆关、平台⽆关、可扩展的序列化结构数据的⽅法&#xff0c;它可⽤ 于&#xff08;数据&#xff09;通信协议、数据存储等。 Protocol Buffers 类⽐于、 XML&#xff0c;是⼀种灵活&#xff0c;⾼效&#xff0c;⾃动化机…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023