【Day57】代码随想录之动态规划_1143最长公共子序列_1035不相交的线_53最大子数组和

文章目录

• • • 动态规划理论基础
    • • 动规五部曲：
      • 出现结果不正确：
    • 1.1143最长公共子序列
    • 2. 1035不相交的线
    • 3. 53最大子数组和

动态规划理论基础

动规五部曲：

1. 确定dp数组 下标及dp[i] 的含义。
2. 递推公式：比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
3. 初始化dp数组。
4. 确定遍历顺序：从前到后or其他。
5. 打印。

出现结果不正确：

1. 打印dp日志和自己想的一样：递推公式、初始化或者遍历顺序出错。
2. 打印dp日志和自己想的不一样：代码实现细节出现问题。

1.1143最长公共子序列

参考文档：代码随想录

分析：
题目要求是公共子序列，所以不要求是连续的。根据dp[i][j]的含义，为什么是表示text1中[0, i-1]和text2中[0, j-1]的最长公共子序列，而不是[0, i] 和 [0, j]。因为刚开始初始化dp[i][0]， dp[j][0]如果是后者，则初始化需要让text1的第一个元素和text2的所有元素对比更新dp[0][j]，同样用text2的第一个元素和text1的所有元素比较是否相等更新dp[i][0]。

这次的dp[i][j]中i和j分别表示text1和text2，是一个比较新的思路，两个数组的状态用二维数组的行和列表示。

dp五部曲：

1. dp[i]含义：[0, i-1], [0, j-1]的最长公共子序列。
2. 递推公式：等：dp[i][j] = dp[i-1][j-1] + 1; 不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
3. 初始化：dp[i][0] = dp[j][0] = 0。
4. 遍历顺序：先text1后text2与先text2后text1都可以。

代码：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //两个字符串text1和text2
        //dp[i][j]: [0, i-1], [0, j-1]的最长公共子序列
        //等：dp[i][j] = dp[i-1][j-1] + 1; 不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

        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][j-1], dp[i-1][j]);
            }
        }

        return dp[text1.size()][text2.size()];
    }
};

2. 1035不相交的线

参考文档：代码随想录

分析：
解决办法和上题同，不相交代表 要控制顺序，指的是字符串1中的子串顺序和字符串2中的子串顺序一致，不要求连续，最多的一致个数就是返回的结果。

代码：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        //dp[i][j]:[0,i-1],[0,j-1]之间有多少的不相交的线
        //保证不相交且某个点只能用一次，即顺序一致，和1143一样
        //dp[i][j] = dp[i-1][j-1] + 1; dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        
        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][j-1], dp[i-1][j]);
                }
            }
        }

        return dp[nums1.size()][nums2.size()];

    }
};

3. 53最大子数组和

参考文档：代码随想录

分析：
最大和是 记录 出来的

暴力搜索：两层for循环，外层for控制数组的开始，内层for控制数组的结束，更新最大数组合值。
贪心：一层for，总和小于零，改变数组的开始，否则，累加，更新最大数组合值。
动态规划：

dp五部曲：

1. dp[i]含义：以i为结尾的最大子序列的和。
2. 递推公式：dp[i] = max(dp[i-1] + nums[i], nums[i]);
3. 初始化：dp[0] = nums[0]; res = nums[0]; 如果集合有元素，数组的最少要有一个元素。
4. 遍历顺序：从前到后。

代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //dp[i]:以i为结尾的最大子序列的和
        //确定最大子序列：开始（动规在不断更新我的开始） 结尾
        if(nums.size() == 0) return 0;

        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int res = dp[0];
        
        for(int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            if(dp[i] > res) res = dp[i];//记录
        }

        return res;
    }
};