1143.最长公共子序列
动规五部曲
dp数组含义：dp[i][j]代表text1中前i个元素部分和text2中前j个元素部分中的公共子序列最大长度。
递推公式：如果遇到text1[i-1] == text2[j-1]就继承dp[i-1][j-1]，并在此基础上+1；
如果text1[i-1] != text2[j-1]，就继承dp[i][j-1], dp[i-1][j]中的最大值。
初始化：全部初始化为0即可
遍历顺序：先text1还是text2都可
最终输出：和连续公共子序列不同，此题输出直接输出dp最右下角的元素
和最长连续公共子序列的区别：一个是连续的，只能在相等的时候继承，不可以删元素退回上一状态；
一个是不连续的，可以删元素，因此在不相等时也可以继承，退回上一状态就相当于删了元素，意思是，这个元素对匹配无作用，dp状态也一样。
class Solution { public: int longestCommonSubsequence(string text1, string text2) { vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1, 0)); for(int i = 1; i<=text1.size(); i++){ for(int j = 1; j<=text2.size(); j++){ if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1]+1; else if(text1[i-1] != text2[j-1]) dp[i][j] = max(dp[i][j-1], dp[i-1][j]); } } return dp[text1.size()][text2.size()]; } };1035.不相交的线
本题与上题完全一样，不相交直线数量和最长公共子序列长度一样。
class Solution { public: int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) { vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0)); for(int i = 1; i<=nums1.size(); i++){ for(int j = 1; j<=nums2.size(); j++){ if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1; else if(nums1[i-1] != nums2[j-1]) dp[i][j] = max(dp[i][j-1], dp[i-1][j]); } } return dp[nums1.size()][nums2.size()]; } };53. 最大子序和
动规五部曲
dp数组含义：dp[i]代表以nums[i]为结尾的连续子数组所具有的最大和
递推公式：dp[i]从两个方向得来，一个是连上以nums[i-1]为结尾的最大和连续子数组，也就是dp[i-1]+nums[i]，一个是不连上前面的（因为dp[i-1]可能是负的），直接只保留nums[i]，二者选最大。
初始化：初始化dp[0]为nums[0]，直接按照dp数组含义即可得到初始化值
遍历顺序：由于要从dp[i-1]向后推，所以顺序遍历，从1遍历到nums.size()-1
最终输出：需要遍历dp数组，寻找最大值
class Solution { public: int maxSubArray(vector<int>& nums) { //以nums[i]为结尾的连续子数组所具有的最大和 vector<int> dp(nums.size(),INT_MIN); dp[0] = nums[0]; int result = dp[0]; for(int i=1; i<nums.size(); i++){ dp[i] = max(nums[i], dp[i-1]+nums[i]); if(dp[i]>result) result = dp[i]; } return result; } };392.判断子序列
花了几分钟写了一下双指针解法，好久没有用双指针，但还是凭借回忆写出来了，感觉之前的努力没有白费。
双指针
class Solution { public: bool isSubsequence(string s, string t) { int j=0; for(int i = 0;i<t.size()&&j<s.size();i++){ if(t[i] == s[j]) j++; } return j==s.size()?true:false; } };动规写法
和最长公共子序列几乎一样，区别就在于，当s[i-1]!= t[j-1]时，不需要找dp[i][j-1]和dp[i-1][j]中的最大值，因为是找t里面有没有s的元素，所以当遇到s和t的元素不同时，不可以从s上退回，也就是不能删s的元素，只能删t的元素。
class Solution { public: bool isSubsequence(string s, string t) { vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0)); for(int i = 1; i<=s.size(); i++){ for(int j = 1; j<=t.size(); j++){ if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1]+1; else if(s[i-1] != t[j-1]) dp[i][j] = dp[i][j-1]; } } return dp[s.size()][t.size()]==s.size()?true:false; } };
