Day53題目

LeetCode.1143最長公共子序列

核心思想:這道題是我動態規劃的啟蒙題目,已經做了很多遍了,dp數組的變化方法是:相同則是左上角+1, 不相同則是上和左中的最大值

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 ++){for(int j = 1;  j <= text2.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]);}}}return dp[text1.length()][text2.length()];}
}

LeetCode1035不相交的線

核心思想:這道題目起始就是求最長公共子序列,代碼基本都不用變

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length + 1][nums2.length + 1];for (int i = 1; i <= nums1.length; i++) {for (int j = 1; j <= nums2.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]);}}}return dp[nums1.length][nums2.length];}
}

LeetCode53.最大子數組的和

核心思想:使用dp存儲目前為止的最大和,如果是負數則存儲0

class Solution {public int maxSubArray(int[] nums) {int max = nums[0];int[] dp = new int[nums.length+1];for(int j = 1 ; j <= nums.length ; j ++){if(dp[j-1] + nums[j-1] <= 0 ){// 雖然是負數,但是也有可能是最大的那個,導致結果就是這個負數,比如 -2 , -1 的結果是 -1max = Math.max(nums[j-1],max);dp[j] = 0;}else{// 否則就相加dp[j] = dp[j-1]+nums[j-1];max = Math.max(dp[j],max);}}return max;}
}