day 43 动态规划

文章目录LeetCode 1143 最长公共子序列LeetCode 1035 不相交的线LeetCode 53 最大子序和LeetCode 392 判断子序列LeetCode 1143 最长公共子序列字符不相等时dp数组的递推可以有dp[i - 1][j]和dp[i][j - 1]得。classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){int[][]dpnewint[text1.length()1][text2.length()1];for(inti1;itext1.length();i){for(intj1;jtext2.length();j){if(text1.charAt(i-1)text2.charAt(j-1)){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]Math.max(dp[i-1][j],dp[i][j-1]);}}}returndp[text1.length()][text2.length()];}}LeetCode 1035 不相交的线实际上时最长公共子序列问题。classSolution{publicintmaxUncrossedLines(int[]nums1,int[]nums2){int[][]dpnewint[nums1.length1][nums2.length1];for(inti1;inums1.length;i){for(intj1;jnums2.length;j){if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]Math.max(dp[i-1][j],dp[i][j-1]);}}}returndp[nums1.length][nums2.length];}}LeetCode 53 最大子序和classSolution{publicintmaxSubArray(int[]nums){int[]dpnewint[nums.length];dp[0]nums[0];for(inti1;inums.length;i){dp[i]Math.max(dp[i-1]nums[i],nums[i]);}intresInteger.MIN_VALUE;for(inti0;inums.length;i){resMath.max(dp[i],res);}returnres;}}LeetCode 392 判断子序列classSolution{publicbooleanisSubsequence(Strings,Stringt){int[][]dpnewint[s.length()1][t.length()1];for(inti1;is.length();i){for(intj1;jt.length();j){if(s.charAt(i-1)t.charAt(j-1)){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]dp[i][j-1];}}}if(dp[s.length()][t.length()]s.length()){returntrue;}else{returnfalse;}}}