代码随想录算法训练营Day-44 动态规划11 | 1143.最长公共子序列、1035.不相交的线、53. 最大子序和、392.判断子序列

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) { vectorvectorint dp(text1.size()1, vectorint(text2.size()1, 0)); for(int i 1; itext1.size(); i){ for(int j 1; jtext2.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(vectorint nums1, vectorint nums2) { vectorvectorint dp(nums1.size()1, vectorint(nums2.size()1, 0)); for(int i 1; inums1.size(); i){ for(int j 1; jnums2.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(vectorint nums) { //以nums[i]为结尾的连续子数组所具有的最大和 vectorint dp(nums.size(),INT_MIN); dp[0] nums[0]; int result dp[0]; for(int i1; inums.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 j0; for(int i 0;it.size()js.size();i){ if(t[i] s[j]) j; } return js.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) { vectorvectorint dp(s.size()1, vectorint(t.size()1, 0)); for(int i 1; is.size(); i){ for(int j 1; jt.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; } };