代码随想录第五十三天

Leetcode 1143. 最长公共子序列

题目链接: 最长公共子序列
自己的思路:没想出来！！！

正确思路:首先这道题由于是涉及到了两个数组（或字符串），所以我们要使用二维dp数组来表示；动规五部曲：1、dp数组的含义：dp[i][j]表示以text1[i-1]和text2[j-1]结尾的最长公共子序列的长度（这里为什么是i-1和j-1前面一些题解已经解释了）；2、递推公式：dp[i][j]是和三个数组有关系的，分别是dp[i-1][j-1]、dp[i][j-1]和dp[i-1][j]，这里就要分情况了，因为我们要判断当前的元素要不要归到最长公共子序列里面去，所以要判断text1[i-1]和text2[j-1]是否相等，如果相等的话，就要在dp[i-1][j-1]基础上加1，如果不相等的话，就要对另外两个求最大值，因为我们的dp[i][j]其实是可以和dp[i][j-1]有关的，我们可以忽略掉text[i-1]这个元素，因为现在text1[i-1]和text2[j-1]并不相等，另一个也是如此！！！3、dp数组的初始化：这里还是和之前那道题一样，全部初始化为0，解释看之前的题；4、遍历顺序：由于dp[i][j]是由前面的数来决定的，所以我们是从前向后遍历；5、打印dp数组：主要用于debug！！！！！

代码:

class Solution {public int longestCommonSubsequence(String text1, String text2) {//转数组，方便操作char[] c1 = text1.toCharArray();char[] c2 = text2.toCharArray();int m = text1.length();int n = text2.length();int[][] dp = new int[m+1][n+1];for (int i = 1;i<=m;i++){for (int j = 1;j<=n;j++){//递推公式if (c1[i-1]==c2[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[m][n];}
}

Leetcode 1035. 不相交的线

题目链接: 不相交的线
自己的思路:和上一个题一模一样！！！！！

正确思路:

代码:

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

Leetcode 53. 最大子数组和

题目链接: 最大子数组和
自己的思路:贪心！！！！我们只在sum大于0的时候给他继续向后加，因为如果小于等于0的话再向后加是没有意义的，只会削弱后的数！！！！

代码:

class Solution {public int maxSubArray(int[] nums) {int sum = 0;int maxvalue = Integer.MIN_VALUE;for (int i=0;i<nums.length;i++){//如果sum大于0才有意义if (sum<=0){sum = nums[i];}else{sum += nums[i];}//更新最大值maxvalue = Math.max(sum,maxvalue);}return maxvalue;}
}

其他思路:动态规划！！！！！！直接动规五部曲：1、dp数组的含义：以nums[i]结尾的最大子序列的和；2、递推公式：主要分析dp[i]和哪些元素有关系，他可能在dp[i-1]的基础上加上当前元素，也可能直接放弃掉之前的累加和，直接令dp[i]=nums[i]，所以要在两者中取较大者；3、dp数组初始化：这里其实只将dp[0]初始化为nums[0]即可，但是因为后面dp[i]的递推公式有一个和nums[i]比较的，我们改成对dp[i]进行比较，所以最开始初始化的时候直接令dp=nums即可！！！！4、遍历顺序：由于后面的状态依赖前面的状态，所以我们采用从前向后遍历的方式；5、打印dp数组：主要用于debug！！！！

代码:

class Solution {public int maxSubArray(int[] nums) {int[] dp = nums;int maxval = nums[0];for (int i =1;i<nums.length;i++){//递推公式dp[i] = Math.max(dp[i-1]+nums[i],dp[i]);maxval = Math.max(maxval,dp[i]);}return maxval;}
}