力扣算法刷题 Day 44

1143 最长公共子序列

题目链接

添加链接描述

思路

dp五部曲：

1. dp数组含义：dp[i][j]表示下标0到i-1 和下标j-1的最长公共子序列
2. 递推：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];
3. 初始化: dp[i][0] = dp[0][j] = 0；
4. 遍历顺序：外层text1，内层text2
5. 模拟：

文章详解

添加链接描述

classSolution{public:intlongestCommonSubsequence(string text1,string text2){intm=text1.length();intn=text2.length();vector<vector<int>>dp(m+1,vector<int>(n+1));for(inti=0;i<=m;i++){dp[i][0]=0;}for(intj=0;j<=n;j++){dp[0][j]=0;}for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(text1[i-1]==text2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}returndp[m][n];}};

1035 不相交的线

题目链接

添加链接描述

思路

分析，本质也是求最长公共子数组。

classSolution{public:intmaxUncrossedLines(vector<int>&nums1,vector<int>&nums2){intm=nums1.size();intn=nums2.size();vector<vector<int>>dp(m+1,vector<int>(n+1));for(inti=0;i<=m;i++){dp[i][0]=0;}for(intj=0;j<=n;j++){dp[0][j]=0;}for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(nums1[i-1]==nums2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}returndp[m][n];}};

53 最大子序和

题目链接

点击此处

思路

方法1 贪心，当前总和小于0直接抛弃
方法2 dp五部曲：

1. dp数组：dp[i] 表示下标从0到i的最大子序和
2. 递推：dp[i] = max(dp[i-1] + nums[i], nums[i]）
3. 初始化：dp[0] = nums[0]
4. 遍历顺序：从左往右
5. 模拟：

392 判断子序列

题目链接

添加链接描述

思路

dp五部曲：

1. dp数组含义：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
2. 递推：if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = dp[i][j - 1];
3. 初始化：0
4. 遍历顺序：从上到下从左到右
5. 模拟：

文章详解

添加链接描述

classSolution{public:boolisSubsequence(string s,string t){vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));for(inti=1;i<=s.size();i++){for(intj=1;j<=t.size();j++){if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=dp[i][j-1];}}if(dp[s.size()][t.size()]==s.size())returntrue;returnfalse;}};