代码随想录刷题记录day46最长公共子序列+不相交的线+最大子数组和

1.dp数组的定义

dp[i][j]表示 以i-1为结尾的字符串text1和以j-1为结尾的字符串2的最长公共子序列长度

2.递推公式

如果text1.charAt(i-1)&＃61;&＃61;text2.charAt(j-1) dp[i][j]&＃61;dp[i-1][j-1]&＃43;1

不相等 判断前一个是否相等 dp[i][j]&＃61;max(dp[i-1][j],dp[i][j-1]);

3.初始化

空数组的最长公共子序列为0

4.遍历顺序

从前往后 从上往下

5.dp数组的打印

代码

class Solution {
public int longestCommonSubsequence(String text1, String text2) {
//1.dp数组的定义
//dp[i][j] 长度为[0,i-1]的字符串text1 和长度为[0,j-1]的字符串text2的最长公共子序列为dp[i][j]
//2.递推公式
//2.1 text[i-1]&＃61;text[j-1] 字符串相同 即找到一个公共的元素&＃xff0c;所以dp[i][j]&＃61;dp[i-1][j-1]&＃43;1
//2.2 text[i-1]!&＃61;text[j-1] 字符串不相同 text1[0,i-2]与text2[0,j-1]的最长公共子序列和
//text1[0,i-1]与text2[0,j-2]的最长公共子序列&＃xff0c;即往前退一格 看是否是相同的
//3.初始化
//dp[i][0] 和空串的最长公共子序列是0
//dp[0][j]&＃61;0
int [][] dp&＃61;new int[text1.length()&＃43;1][text2.length()&＃43;1];
//4.递推顺序 从前往后 从上往下
for(int i&＃61;1;i<&＃61;text1.length();i&＃43;&＃43;){
for(int j&＃61;1;j<&＃61;text2.length();j&＃43;&＃43;){
if(text1.charAt(i-1)&＃61;&＃61;text2.charAt(j-1))dp[i][j]&＃61;dp[i-1][j-1]&＃43;1;
else{
dp[i][j]&＃61;Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}


其实就是求最长的公共的子序列&＃xff0c;和上一题的思路是一样的&＃xff0c;只不过上一题是字符串的行式&＃xff0c;这题是数组了。

代码

class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
//就是求最长公共子序列
//1.dp数组的定义
//dp[i][j]表示[0,i-1]的数组1和[0,j-1]的数组2的最长连续公共子序列的长度
//2.递推公式
//if(nums1[i-1]&＃61;&＃61;num2[j-1]) dp[i][j]&＃61;dp[i-1][j-1]&＃43;1
//else dp[i][j]&＃61;Math.max(dp[i-1][j],dp[i][j-1]);
//初始化 0表示序列为空 都初始化为0
int[][] dp&＃61;new int[nums1.length&＃43;1][nums2.length&＃43;1];
for(int i&＃61;1;i<&＃61;nums1.length;i&＃43;&＃43;){
for(int j&＃61;1;j<&＃61;nums2.length;j&＃43;&＃43;){
if(nums1[i-1]&＃61;&＃61;nums2[j-1]) dp[i][j]&＃61;dp[i-1][j-1]&＃43;1;
else dp[i][j]&＃61;Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[nums1.length][nums2.length];
}
}


1.dp数组的定义

dp[i]表示以[0,i]区间的最大子数组的和

2.递推公式

if(nums[i]>nums[i-1]) dp[i]&＃61;dp[i-1]&＃43;nums[i];

或者说是 nums[i]重新开始计数

3.初始化

dp[0]&＃61;nums[i]

4.遍历顺序

从前到后

5.数组的打印

因为是要记录最大&＃xff0c;所以需要一个变量来维护。

class Solution {
// public int maxSubArray(int[] nums) {
// //连续数组的最大和
// //贪心算法
// int count&＃61;0;
// int res&＃61;Integer.MIN_VALUE;
// for(int i&＃61;0;i
// count&＃43;&＃61;nums[i];
// if(count>res){
// res&＃61;count;
// }
// if(count<&＃61;0) count&＃61;0;//重新开始计数
// }
// return res;
// }
public int maxSubArray(int[] nums) {
//连续数组的最大和
//动态规划
//1.dp数组的定义
//dp[i]表示[0,i]区间的最大连续子数组的和
//2.递推公式
//if(nums[i]>nums[i-1]) dp[i]&＃61;dp[i-1]&＃43;nums[i]
//nums[i] 从头开始
//3.初始化
int [] dp&＃61;new int[nums.length];
dp[0]&＃61;nums[0];
int res&＃61;dp[0];
for(int i&＃61;1;i<nums.length;i&＃43;&＃43;){
dp[i]&＃61;Math.max(dp[i-1]&＃43;nums[i],nums[i]);
if(dp[i]>res){
res&＃61;dp[i];
}
//System.out.println(dp[i]);
}
return res;

}
}