目录
1143.最长公共子序列
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难
1035.不相交的线
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难
53. 最大子序和
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难
1143.最长公共子序列
力扣题目链接(opens new window)
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列,则返回 0。
示例 1:
- 输入:text1 = "abcde", text2 = "ace"
- 输出:3
- 解释:最长公共子序列是 "ace",它的长度为 3。
示例 2:
- 输入:text1 = "abc", text2 = "abc"
- 输出:3
- 解释:最长公共子序列是 "abc",它的长度为 3。
示例 3:
- 输入:text1 = "abc", text2 = "def"
- 输出:0
- 解释:两个字符串没有公共子序列,返回 0。
提示:
- 1 <= text1.length <= 1000
- 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符
看到题目的第一想法
用动态规划,dp[][]为二维数组
dp的定义:dp[i][j] ,nums1 的[0,i-1], nums2的[0,j-1] 的最长公共子序列的长度
递推公式
我的递推公式有错,我想着是再遍历i和j,把所有和加起来最大值替代dp[i][j],其实是没有结合dp数组的定义来写dp的递推公式
看到代码随想录之后的想法
用动态规划
确定dp数组和每个下标的含义
dp[i][j]记录末尾为i-1和j-1的最长的子序列的长度
确定递推公式
要从递推公式来进行考虑
若text1[i] = text2[j] 则在之前的基础上+1
dp[i][j] = dp[i-1][j-1]+1;
若text1[i] != text2[j] 则等于之前的最大值
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
dp数组初始化
因为dp[i][j] 代表0~i-1,0~j-1的最大子序列,则不需要定义dp[i][0],dp[0][j],因为0 代表-1没有意义
确定遍历顺序
从前往后,从上往下
举例推导dp数组
打印dp数组
打印最后一个元素
自己实现过程中遇到的困难
自己需要注意i-1和j-1这个点,同时for循环的条件需要 i<= j<= 不要忘了等号
要结合dp的定义来写递推公式
字符串用char[] 比较好写
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
//二维数组?dp[i][j]记录text1下标i到text2下标j的长度
//上一题是连续,这一题不连续
//dp[i][j]后遍历 若 text1[i] = text2[j]
//则遍历到i,j,不断更新dpij的最大值
//text1 text2
/*int[][] dp = new int[text1.length()+1][text2.length()+1];
char[] c1 = text1.toCharArray();
char[] c2 = text2.toCharArray();
int max = 0;
for(int i=1;i<=text1.length();i++){
for(int j=1;j<text2.length();j++){
if(c1[i-1]==c2[j-1]){
for(int x=1;x<i;x++){
for(int y=1;y<j;y++){
dp[i][j] = Math.max(dp[x][y]+1,dp[i][j]);
}
}
}
max = max>dp[i][j]?max:dp[i][j];
}
}
return max;*/
//卡哥做法:dp[i][j]代表0~i-1 0~j-1最长公共子序列的长度
//确定递推公式
//从dp的定义处罚,相当于两者都往前走一步的最大值+1
// 若text1[i] = text2[j] dp[i][j] = dp[i-1][j-1]+1
// 若不相等 则dp[i][j] 要获取之前两者最长公共子序列的最大值
//dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
//dp数组初始化
//都为0
//确定遍历顺序
//从前往后
//举例推导dp数组
int[][] dp = new int[text1.length()+1][text2.length()+1];
char[] c1 = text1.toCharArray();
char[] c2 = text2.toCharArray();
for(int i=1;i<=text1.length();i++){
//少打了个=,要去debug
for(int j=1;j<=text2.length();j++){
if(c1[i-1]==c2[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}
if(c1[i-1]!=c2[j-1]){
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
1035.不相交的线
力扣题目链接(opens new window)
我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在,我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线,只要 A[i] == B[j],且我们绘制的直线不与任何其他连线(非水平线)相交。
以这种方法绘制线条,并返回我们可以绘制的最大连线数。
看到题目的第一想法
和上一道题一样的思路,直接写,通过了
看到代码随想录之后的想法
用动态规划
确定dp数组和每个下标的含义
dp[i][j]记录末尾为i-1和j-1的最长的子序列的长度
确定递推公式
要从递推公式来进行考虑
若text1[i] = text2[j] 则在之前的基础上+1
dp[i][j] = dp[i-1][j-1]+1;
若text1[i] != text2[j] 则等于之前的最大值
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
dp数组初始化
因为dp[i][j] 代表0~i-1,0~j-1的最大子序列,则不需要定义dp[i][0],dp[0][j],因为0 代表-1没有意义
确定遍历顺序
从前往后,从上往下
举例推导dp数组
打印dp数组
打印最后一个元素
自己实现过程中遇到的困难
自己需要注意i-1和j-1这个点,同时for循环的条件需要 i<= j<= 不要忘了等号
要结合dp的定义来写递推公式
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
//二维数组?dp[i][j]记录text1下标i到text2下标j的长度
//上一题是连续,这一题不连续
//dp[i][j]后遍历 若 text1[i] = text2[j]
//则遍历到i,j,不断更新dpij的最大值
//text1 text2
/*int[][] dp = new int[text1.length()+1][text2.length()+1];
char[] c1 = text1.toCharArray();
char[] c2 = text2.toCharArray();
int max = 0;
for(int i=1;i<=text1.length();i++){
for(int j=1;j<text2.length();j++){
if(c1[i-1]==c2[j-1]){
for(int x=1;x<i;x++){
for(int y=1;y<j;y++){
dp[i][j] = Math.max(dp[x][y]+1,dp[i][j]);
}
}
}
max = max>dp[i][j]?max:dp[i][j];
}
}
return max;*/
//卡哥做法:dp[i][j]代表0~i-1 0~j-1最长公共子序列的长度
//确定递推公式
//从dp的定义处罚,相当于两者都往前走一步的最大值+1
// 若text1[i] = text2[j] dp[i][j] = dp[i-1][j-1]+1
// 若不相等 则dp[i][j] 要获取之前两者最长公共子序列的最大值
//dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
//dp数组初始化
//都为0
//确定遍历顺序
//从前往后
//举例推导dp数组
int[][] dp = new int[text1.length()+1][text2.length()+1];
char[] c1 = text1.toCharArray();
char[] c2 = text2.toCharArray();
for(int i=1;i<=text1.length();i++){
//少打了个=,要去debug
for(int j=1;j<=text2.length();j++){
if(c1[i-1]==c2[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}
if(c1[i-1]!=c2[j-1]){
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
53. 最大子序和
力扣题目链接(opens new window)
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
- 输入: [-2,1,-3,4,-1,2,1,-5,4]
- 输出: 6
- 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
看到题目的第一想法
之前用贪心写过,贪心的思路是找非负的sum,然后开始累加
dp 的思路
dp[i]以i为终点的最大和
递推公式:dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
初始化:dp[0] = nums[0]
打印:整个dp中的最大值
看到代码随想录之后的想法
用动态规划,和我的思路一样
自己实现过程中遇到的困难
注意下边界条件文章来源:https://www.toymoban.com/news/detail-820526.html
比较顺利,不过贪心的时候需要注意sum的调整文章来源地址https://www.toymoban.com/news/detail-820526.html
class Solution {
public int maxSubArray(int[] nums) {
/*//动态规划
//确定dp数组和下标的含义
//到达当前下标的最大和
//确定递推公式
//dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
//dp数组初始化
//dp[0]=nums[0]
//举例dp数组
if(nums.length==1){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0]=nums[0];
int max=dp[0];
for(int i=1;i<nums.length;i++){
dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
max=max>dp[i]?max:dp[i];
}
return max;*/
//贪心从非负的开始找,若sum<0 则继续往下找第一个非负的
int result = Integer.MIN_VALUE;
int sum=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
if(sum>result){
result=sum;
}
if(sum<0){
sum=0;
}
}
return result;
}
}
到了这里,关于动态规划Day14(子序列第二天)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!