微信网站上传图片,营销网站制作免费咨询,上海电信网站备案,阳东网站seo代码随想录算法训练营Day56|动态规划14 文章目录 代码随想录算法训练营Day56|动态规划14一、1143.最长公共子序列二、 1035.不相交的线三、53. 最大子序和 动态规划 一、1143.最长公共子序列
class Solution {public int longestCommonSubsequence(String text1, String text2…代码随想录算法训练营Day56|动态规划14 文章目录 代码随想录算法训练营Day56|动态规划14一、1143.最长公共子序列二、 1035.不相交的线三、53. 最大子序和 动态规划 一、1143.最长公共子序列
class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp new int[text1.length() 1][text2.length() 1];for (int i 1 ; i text1.length() ; i) {char char1 text1.charAt(i - 1);for (int j 1; j text2.length(); j) {char char2 text2.charAt(j - 1);if (char1 char2) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[text1.length()][text2.length()];}
}
二、 1035.不相交的线 class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int len1 nums1.length;int len2 nums2.length;int[][] dp new int[len1 1][len2 1];for (int i 1; i len1; i) {for (int j 1; j len2; 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]);}}}return dp[len1][len2];}
}三、53. 最大子序和 动态规划
class Solution {public static int maxSubArray(int[] nums) {if (nums.length 0) {return 0;}int res nums[0];int[] dp new int[nums.length];dp[0] nums[0];for (int i 1; i nums.length; i) {dp[i] Math.max(dp[i - 1] nums[i], nums[i]);res res dp[i] ? res : dp[i];}return res;}}
