JLUVicent

1143最长公共子序列&53最大子数组和&1035不相交的线

 
  • 2023年 04月08日
  • 0 阅读

day53

1143.最长公共子序列

题目链接：1143. 最长公共子序列

解题思路：参考 视频

1.确定dp数组及下标含义

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

2.确定递推公式

主要就是两大情况： 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]);$

3.dp数组初始化

$dp[i][0]和dp[0][j]$可以理解为非法情况，赋值为0即可，其余全部赋值为任何值都可以，之后会覆盖掉

4.确定遍历顺序

1143.最长公共子序列

5.打印dp数组

1143.最长公共子序列1

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int t1 = text1.size();
        int t2 = text2.size();
        vector<vector<int>> dp(t1+1,vector<int>(t2+1,0));
        for( int i = 1; i <= t1; i++){
            for( int j = 1; j <= t2; 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[t1][t2];
    }
};

1035.不相交的线

题目链接：1035. 不相交的线

解题思路：和最长公共子序列思路一模一样

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
        for( int i = 1; i <= n1; i++){
            for( int j = 1; j <= n2; 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[n1][n2];
    }
};

53.最大子数组和

题目链接：53. 最大子数组和

解题思路：参考 视频

确定dp数组下标及含义

dp[i]：包括下标i的最大连续子序列的和为dp[i]

确定递推公式

dp[i] = max( dp[i-1]+nums[i],nums[i]);

初始化

dp[0] = nums[0];

遍历顺序

从前向后，注意最后取值是取最大值

打印dp数组

53.最大子序和（动态规划）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 贪心
        // int result = INT_MIN;
        // int sum = 0;
        // for( int i = 0; i < nums.size(); i++){
        //     sum += nums[i];
        //     result = sum > result ? sum:result;
        //     sum = sum > 0 ? sum : 0 ;
        // }
        // return result;
        // 动态规划
        //时间：O(n)
        //空间：O(n)
        if( nums.size() == 1) return nums[0];
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        // int result = INT_MIN;
        int result = dp[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;
    }
};
搜索