阜阳市城乡建设局网站,vc域名建站的网站,徐州市鼓楼区建设局网站,福永镇网站建设代码随想录第五十三天 Leetcode 1143. 最长公共子序列Leetcode 1035. 不相交的线Leetcode 53. 最大子数组和 Leetcode 1143. 最长公共子序列
题目链接: 最长公共子序列 自己的思路:没想出来#xff01;#xff01;#xff01;
正确思路:首先这道题由于是涉及到了两个数组
正确思路:首先这道题由于是涉及到了两个数组或字符串所以我们要使用二维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[m1][n1];for (int i 1;im;i){for (int j 1;jn;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[m1][n1];for (int i1;im;i){for (int j 1;jn;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 i0;inums.length;i){//如果sum大于0才有意义if (sum0){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]进行比较所以最开始初始化的时候直接令dpnums即可4、遍历顺序由于后面的状态依赖前面的状态所以我们采用从前向后遍历的方式5、打印dp数组主要用于debug
代码:
class Solution {public int maxSubArray(int[] nums) {int[] dp nums;int maxval nums[0];for (int i 1;inums.length;i){//递推公式dp[i] Math.max(dp[i-1]nums[i],dp[i]);maxval Math.max(maxval,dp[i]);}return maxval;}
}
