1143.最长公共子序列
本题一开始以为是和前面那个一维递增子序列一样，dp数组的[i][j]表示的是以i，j为结尾的最长公共子序列，然后用两个for循环去前面找前缀对应的最大值，这样写出来的代码算上遍历总共要4次for循环，结果当然是会超时，并且我的代码还不知道哪里有问题，得不到正确的结果。
那么为什么本题用的是卡哥那样的定义方法，即：
1 如果当前位置相同，就是i-1，j-1位置的值+1
2 否则，取i-1，j和i，j-1的最大值。
这里引用一段在b站看到的评论的解释，由文无cc_大佬提供：
求递增序列的时候，因为要求序列有序，所以必须确定序列最后一个元素的值，才能比较新加入序列的元素是不是递增的。求相等序列的时候，如果求连续相等子序列，则还是要确定序列最后一个元素的值；但是本题求的是不必连续的相等子序列，就不需要知道序列最后一个元素的值，只要知道范围内相等的序列长度就行，新来的相等元素可以直接加在序列后面
也就是说我在算最长公共子序列的时候，是不需要去看序列最后一个元素到底是什么的，所以也就无需将dp数组定义成以i，j为结尾。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size();int n = text2.size();vector<vector<int>> dp(m+1, vector<int>(n+1));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][j-1], dp[i-1][j]);}}}return dp[m][n];}
};1035.不相交的线
还真和上一题一模一样，错的也一一模一样：比较的时候要判断nums1[i-1] == nums2[j-1]而不是nums1[i] == nums2[j]，隔了一会再写就又忘了。
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();vector<vector<int>> dp(m+1, vector<int>(n+1));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. 最大子序和
说实在的一看到这个题满脑子都是贪心，不贪心反而不会做了，自己仿照着贪心的写法写了个dp数组，写出来就是对的。解析里说dp比较直观，贪心比较难想，但我感觉这俩是一模一样的思路，只是写法不一样而已。
class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n);dp[0] = nums[0];if(n==1){return nums[0];}int result = dp[0];for(int i=1; i<n; i++){dp[i] = max(dp[i-1]+nums[i], nums[i]);if(dp[i] > result){result = dp[i];}}return result;}
};392. 判断子序列
本题也是一样，满脑子双指针，让我用dp写一个m*n复杂度的代码感觉就像杀了我一样难受，总是感觉这里能优化，那里能改一下，结果改了半天，循环逻辑倒是解决了，但是一些特殊的初始化和边界条件又出现问题了。
最后老老实实写了一个m*n复杂度的代码，还是这个适合我，之前简化了半天完全给自己绕进去了。
class Solution {
public:bool isSubsequence(string s, string t) {int m = s.size();int n = t.size();if(m==0){return true;}vector<vector<int>> dp(m+1, vector<int>(n+1));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;}
};
