1143. 最长公共子序列 - 力扣（LeetCode）
思路：动态规划，分为三种状态。当两个字符相同时同时增长，不相同时由i-1的和j-1的状态进行推导
重点： 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]);
}
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m=text1.size(),n=text2.size();
vector<vector<int>>dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;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]);//前i-1和前j-1比较
}
}
}
return dp[m][n];
}
};1035. 不相交的线 - 力扣（LeetCode）
思路：同上，理解题意就是最长公共子序列
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size(),n=nums2.size();
vector<vector<int>>dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;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[m][n];
}
};53. 最大子数组和 - 力扣（LeetCode）
思路：判断每个以nums[i]结尾的数的累加和，找最大值
重点：dp[i]=max(dp[i-1]+nums[i],nums[i]);
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
vector<int>dp(n,0);
dp[0]=nums[0];
int ans=dp[0];//最初的最大和
for(int i=1;i<n;i++){
//因为累加和可能为负数
dp[i]=max(dp[i-1]+nums[i],nums[i]);//当以前的累加和与现在的数比较
if(dp[i]>ans){
ans=dp[i];
}
}
return ans;
}
};392. 判断子序列 - 力扣（LeetCode）
思路：依次判断s的字符是否为t的子序列，当最长子序列长度为s的长度时，表示s是t的子序列
class Solution {
public:
bool isSubsequence(string s, string t) {
int m=s.size(),n=t.size();
vector<vector<int>>dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;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];//相当于长字符串删除一个字符后的前一个状态
}
}
}
return dp[m][n]==m?true:false;//最长等于m的长度就说明s是t的子序列
}
};总结
子序列问题，判断dp数组的递推就行了
