第九章 动态规划part11
1143.最长公共子序列
体会一下本题和 718. 最长重复子数组 的区别
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ
https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] ctext1 = text1.toCharArray();
char[] ctext2 = text2.toCharArray();
int[][] dp = new int[ctext1.length+1][ctext2.length+1];
int result = 0;
for(int i = 1; i <= ctext1.length; i ++){
for(int j = 1; j <= ctext2.length; j ++){
if(ctext1[i-1] == ctext2[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]);
if(dp[i][j] > result) result = dp[i][j];
}
}
return result;
}
}
1035.不相交的线
其实本题和 1143.最长公共子序列 是一模一样的，大家尝试自己做一做。
视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP
https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length+1][nums2.length+1];
int result = 0;
for(int i = 1; i <= nums1.length; i ++){
for(int j = 1; j <= nums2.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]);
if(dp[i][j] > result) result = dp[i][j];
}
}
return result;
}
}
53. 最大子序和
这道题我们用贪心做过，这次 再用dp来做一遍
视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5
class Solution {
public int maxSubArray(int[] nums) {
// dp[i] 以numi为结束的最大连续子数组和
int[] dp = new int[nums.length];
dp[0] = nums[0];
int result = nums[0];
for(int i = 1; i < nums.length; i ++ ){
dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
if(result < dp[i]) result = dp[i];
}
return result;
}
}
392.判断子序列
这道题目算是 编辑距离问题 的入门题目（毕竟这里只是涉及到减法），慢慢的，后面就要来解决真正的 编辑距离问题了
https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html
class Solution {
public boolean isSubsequence(String s, String t) {
char[] s1 = s.toCharArray();
char[] t1 = t.toCharArray();
int[][] dp = new int[s1.length+1][t1.length+1];
int result = 0;
for(int i = 1; i <= s1.length; i ++){
for(int j = 1; j <= t1.length; j ++){
if(s1[i-1] == t1[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]);
if(dp[i][j] > result) result = dp[i][j];
}
}
int length = s1.length;
if(result == length) return true;
return false;
}
}
实际：
