leetcode53、300、1143—— 子序列和子数组问题（动态规划）

子序列和子数组

1、子序列

1.1、最长上升子序列

题目链接
给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。

进阶:

• 你能将算法的时间复杂度降低到 O(n log n) 吗?

1.1.1、思路

1、状态

这里的状态就是字符串的长度，随着索引的变化，对应 该索引下最长子序列长度的变化状态。

2、明确 dp 数组的含义

dp[i] ：以 nums[i] 这个数结尾的最长递增子序列的长度。

如何 dp 数组吗？我们可以假设 dp[0...i-1] 都已经被算出来了，然后问自己：怎么通过这些结果算出 dp[i]？

根据刚才我们对 dp 数组的定义，现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。

nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。
3、定义 base case

dp[i] 初始值为 1，因为以 nums[i] 结尾的最长递增子序列起码要包含它自己。

4、状态转移方程

for(int i = 0;i < len;i++)
        {
            for(int j = 0;j < i;j++)
            {
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i],dp[j]+1);
            }
        }

1.1.2、题解

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if(len < 2)
            return len;
        vector<int>dp(len,1);
        for(int i = 0;i < len;i++)
        {
            for(int j = 0;j < i;j++)
            {
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i],dp[j]+1);
            }
        }
        int res = 0;
        for(int  i = 0;i < len;i++)
        {
            res = max(res,dp[i]);
        }
        return res;
    }
};

1.2、最长公共子序列

原题链接
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• 输入的字符串只含有小写英文字符。

1.2.1、思路

1、状态
这里的状态就是字符串的长度，随着长度的变化，对应该长度下公共子序列长度的变化状态。

2、明确 dp 数组的含义
对于字符串 s1 和 s2，一般来说都要构造一个这样的 DP table：

dp[i][j] 的含义是：对于 s1[1..i] 和 s2[1..j]，它们的 LCS 长度是 dp[i][j]。

d[2][4] 的含义就是：对于 "ac" 和 "babc"，它们的 LCS 长度是 2。我们最终想得到的答案应该是 dp[3][6]。

3、定义 base case
让索引为 0 的行和列表示空串，dp[0][..] 和 dp[..][0] 都应该初始化为 0，这就是 base case。

比如说，按照刚才 dp 数组的定义：

dp[0][3]=0 的含义是：对于字符串 "" 和 "bab"，其 LCS 的长度为 0。因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0。

4、状态转移方程
状态转移说简单些就是做选择，

比如说这个问题，是求 s1 和 s2 的最长公共子序列，不妨称这个子序列为 lcs。那么对于 s1 和 s2 中的每个字符，有什么选择？很简单，两种选择，要么在 lcs 中，要么不在。

这个「在」和「不在」就是选择，关键是，应该如何选择呢？
如果某个字符应该在 lcs 中，那么这个字符肯定同时存在于 s1 和 s2 中，因为 lcs 是最长公共子序列嘛。

所以本题的思路是这样：

• 用两个指针 i 和 j 从后往前遍历 s1 和 s2，如果 s1[i]==s2[j]，那么这个字符一定在 lcs 中，找到一个 lcs 中的字符，同时将 i， j 向前移动一位，并给 lcs 的长度加1
• 否则的话，s1[i] 和 s2[j] 这两个字符至少有一个不在 lcs 中，需要丢弃一个，取更大的结果。

	for(int i = 1;i <= len1;i++)
        {
            for(int j = 1;j <= len2;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]);
            }
        }

1.2.2、题解

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.size(),len2 = text2.size();
        if(len1 == 0 || len2 == 0)
            return 0;
        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(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[len1][len2];
    }
};

2、子数组

明确子数组和子序列最大的区别：子数组是一段连续的子集，子序列是离散的子集

2.1、连续子数组的最大和

原题链接
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

2.2、思路

1、状态
这里的状态就是数组的长度，随着长度的变化，对应 该长度下连续子数组和的变化状态。

2、明确 dp 数组的含义：这里需要注意
按照我们常规的动态规划思路，一般是这样定义 dp 数组：

nums[0..i] 中的「最大的子数组和」为 dp[i]。

如果这样定义的话，整个 nums 数组的「最大子数组和」就是 dp[n-1]。如何找状态转移方程呢？

按照数学归纳法，假设我们知道了 dp[i-1]，如何推导出 dp[i] 呢？

如下图，按照我们刚才对 dp 数组的定义，dp[i] = 5 ，也就是等于 nums[0…i] 中的最大子数组和：

实际上是不行的，因为子数组一定是连续的，按照我们当前 dp 数组定义，并不能保证 nums[0..i] 中的最大子数组与 nums[i+1] 是相邻的，也就没办法从 dp[i] 推导出 dp[i+1]。

重新定义 dp 数组的含义：

以 nums[i] 为结尾的「最大子数组和」为 dp[i]。

dp[i] 有两种「选择」：

• 要么与前面的相邻子数组连接，形成一个和更大的子数组；
• 要么不与前面的子数组连接，自成一派，自己作为一个子数组。

由此引出状态转移方程

3、 base case
第一个元素前面没有子数组

dp[0] = nums[0];

4、状态转移方程：就是做选择
dp[i] 有两种「选择」：

• 要么与前面的相邻子数组连接，形成一个和更大的子数组；
• 要么不与前面的子数组连接，自成一派，自己作为一个子数组。

for (int i = 1; i < n; i++) {
        dp[i] = max(nums[i], nums[i] + dp[i - 1]);
        //注意前面是nums[i],不是dp[i - 1]
    }

2.3、题解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        vector<int>dp(len,0);
        dp[0] = nums[0];
        for(int i = 1;i < len;i++)
            dp[i] = max(nums[i],dp[i - 1] + nums[i]);
        int res = INT_MIN;
        for(int i = 0;i < len;i++)
        {
            res = max(res,dp[i]);
        }
        return res;
    }
};

状态压缩进行空间维度的优化：

注意到 dp[i] 仅仅和 dp[i-1] 的状态有关，那么我们可以进行「状态压缩」，将空间复杂度降低：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
       int dp_0 = nums[0];
        int dp_1 = 0, res = dp_0;
        for(int i = 1;i < len;i++)
        {
            dp_1 = max(nums[i], nums[i] + dp_0);
            dp_0 = dp_1;//记录前一个状态，毕竟只和前一个状态有关
            res = max(res, dp_1); 
        }
        return res;
    }
};

参考