教育培训网站模板下载,自己做商务网站有什么利弊,电子商务网站建设考试简答题,秦皇岛项目建设LeetCode T1143 最长公共子序列
题目链接:1143. 最长公共子序列 - 力扣#xff08;LeetCode#xff09; 题目思路: 动规五部曲分析 1.确定dp数组的含义 这里dp数组的含义是结尾分别为i-1,j-1的text1和text2的最长公共子序列长度 至于为什么是i-1,j-1我之前已经说过了,这里再…
LeetCode T1143 最长公共子序列
题目链接:1143. 最长公共子序列 - 力扣LeetCode 题目思路: 动规五部曲分析 1.确定dp数组的含义 这里dp数组的含义是结尾分别为i-1,j-1的text1和text2的最长公共子序列长度 至于为什么是i-1,j-1我之前已经说过了,这里再说一次,因为如果定义为i和j 的话就需要比较两个字符串的首字母分别是否相等来初始化dp[0][i]和dp[0][j],因为这样定义的话dp[0][j]和 dp[i][0]就没有含义,省去了初始化的部分 2.确定递推公式 dp[i][j]可以从dp[i-1][j-1],dp[i-1][j]和dp[i][j-1]三个推出来 当text1[i]和text2[j]相等时,就是dp[i-1][j-1]1 当两者不相等时,就是剩下两者的最大值 3.初始化dp数组 无需初始化,原因上面说清楚了,而剩下的所有值都会被覆盖,所以无所谓 4.遍历顺序 从前向后,因为后面的数据是前面产生的 5.打印排错 题目代码:
class Solution {public int longestCommonSubsequence(String text1, String text2) {int dp[][] new int[text1.length()1][text2.length()1];for(int i 1;itext1.length();i){char c text1.charAt(i-1);for(int j 1;jtext2.length();j){char c2 text2.charAt(j-1);if(c c2){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()];}
}
LeetCode T1135 不相交的线
题目链接:1035. 不相交的线 - 力扣LeetCode 题目思路: 这里我们可以将这一题的思路转化一下,其实就和第一题的思路一模一样,题目要求两条对应的线不能相交,其实就是交代了有序性,这也满足了第一题的条件,求最长公共子序列,所以不做过多赘述. 题目代码:
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp new int[nums1.length1][nums2.length1];int res 0;for(int i 1;inums1.length;i){for(int j 1;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]);}}}return dp[nums1.length][nums2.length];}
}
LeetCode T53 最大子数组和
题目链接:53. 最大子数组和 - 力扣LeetCode
题目思路: 动规五部曲分析 1.确定dp数组的含义 这里dp数组的含义是i位置之前(包括i在内)最大连续子序列之和 这一题我们在之前也用过贪心的思路来求解,见文章 代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和-CSDN博客 2.确定递推公式 dp[i][j]可以从前面一个推出,如果累计和小于当前的nums[i],就从nums[i]开始记录 3.初始化dp数组 dp[0] nums[0];不能初始化为0,因为有一个元素的情况存在 4.遍历顺序 从前向后遍历即可 5.打印排错 注意:这题的结果不在结尾取,要定义一个res在赋值的时候顺便记录最大值 题目代码:
class Solution {public int maxSubArray(int[] nums) {int[] dp new int[nums.length];dp[0] nums[0];int res dp[0];for(int i 1;inums.length;i){dp[i] Math.max(dp[i-1]nums[i],nums[i]);res Math.max(res,dp[i]);}return res;}
}
