最长公共子序列
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n1=text1.size();int n2=text2.size();int res=0;vector<int> dp(n2,0);for(int i=0;i<n1;i++){for(int j=n2-1;j>=0;j--){if(text2[j]==text1[i]){for(int k=0;k<j;k++){dp[j]=max(dp[j],1+dp[k]);}if(j==0)dp[0]=1;}if(res<dp[j])res=dp[j];}}return res;}
};
时间复杂度比较高，可以用二维dp数组
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n1=text1.size();int n2=text2.size();int res=0;vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));for(int i=1;i<n1+1;i++){for(int j=1;j<n2+1;j++){if(text1[i-1]==text2[j-1]){dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]);}else{dp[i][j]=max(dp[i][j-1],dp[i-1][j]);}}} return dp[n1][n2];}
};
不相交的线
- 和上面一模一样
最大子序列和
class Solution {
public:int maxSubArray(vector<int>& nums) {// int res=-__INT32_MAX__;// int max=res;// for(int num:nums){// if(res<0)res=num;// else{// res+=num;// }// if(res>max)max=res;// }// return max;int dp=nums[0];int res=dp;for(int i=1;i<nums.size();i++){if(dp>0){dp+=nums[i];}else{dp=nums[i];}if(res<dp)res=dp;}return res;}
};
贪心的代码和动态规划写出来是一样的，但思考方式不同
判断子序列
class Solution {
public:bool isSubsequence(string s, string t) {int n1=s.size();int n2=t.size();int len=0;vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));for(int i=1;i<n1+1;i++){for(int j=1;j<n2+1;j++){if(s[i-1]==t[j-1]){dp[i][j]=1+dp[i-1][j-1];}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}if(len<dp[i][j])len=dp[i][j];}}if(len==n1)return 1; return 0;}
};
