第九章 动态规划part10
300.最长递增子序列
今天开始正式子序列系列，本题是比较简单的，感受感受一下子序列题目的思路。
视频讲解：https://www.bilibili.com/video/BV1ng411J7xP
https://programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html
class Solution {
public int lengthOfLIS(int[] nums) {
//dp[i] 以i为结尾的最大递增序列长度
int[] dp = new int[nums.length];
for(int i = 0; i < nums.length; i ++){
dp[i] = 1;
}
for(int i = 1; i < nums.length; i ++){
for(int j = 0; j < i; j ++){
if(nums[i] > nums[j]) dp[i] = dp[j] + 1;
}
}
int result = 0;
for(int i = 0; i < nums.length; i ++){
if(dp[i] > result) result = dp[i];
}
return result;
}
}
输入
nums =
[0,1,0,3,2,3]
输出
3
预期结果
4
问题;dp[i]的值动态更新
class Solution {
public int lengthOfLIS(int[] nums) {
//dp[i] 以i为结尾的最大递增序列长度
int[] dp = new int[nums.length];
for(int i = 0; i < nums.length; i ++){
dp[i] = 1;
}
for(int i = 1; i < nums.length; i ++){
for(int j = 0; j < i; j ++){
if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int result = 0;
for(int i = 0; i < nums.length; i ++){
if(dp[i] > result) result = dp[i];
}
return result;
}
}
674. 最长连续递增序列
本题相对于昨天的动态规划：300.最长递增子序列 最大的区别在于“连续”。 先尝试自己做做，感受一下区别
视频讲解：https://www.bilibili.com/video/BV1bD4y1778v
class Solution {
public int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
for(int i = 0; i < nums.length; i ++){
dp[i] = 1;
}
for(int i = 1; i < nums.length; i ++){
if(nums[i] > nums[i-1]) dp[i] = dp[i - 1] + 1;
else dp[i] = 1;
}
int result = 0;
for(int i = 0; i < nums.length; i ++){
if(dp[i] > result) result = dp[i];
}
return result;
}
}
718. 最长重复子数组
稍有难度，要使用二维dp数组了
视频讲解：https://www.bilibili.com/video/BV178411H7hV
https://programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int result = 0;
for(int i = 0; i < nums1.length; i ++){
for(int j = 0; j < nums2.length; j ++){
if(nums1[i] == nums2[j]) dp[i+1][j+1] = dp[i][j] + 1;
if(dp[i+1][j+1] > result) result = dp[i+1][j+1];
}
}
return result;
}
}
