Day44 力扣动态规划 : 300.最长递增子序列｜674. 最长连续递增序列 ｜ 718. 最长重复子数组

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

第一印象

我直接看题解感受子序列题目的思路

看完题解的思路

dp

这个系列的dp数组的含义是：

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

递推公式

这道题的递推公式不像之前的dp问题

I 和 I - 1 进行比较。

因为最长子序列是不连续的，比如 1 2 3 1 4，最长应该是 1 2 3 4

而以 1 为结尾的最长递增子序列是 1，也就是dp[3] = 1。

以 4 为结尾的最长递增子序列是 4， 他是dp[2] + 1 = 3 + 1 = 4

所以这道题比较的是，在0～i-1里对每个元素 j，如果 i 比这个元素 j 要大，那么对与当前的 j 来说，i就是一个更大的递增子序列，长度是dp[j] + 1.

但也不是每次都要更新到dp[i] ，因为求的是最大的子序列，只有当前元素 j 算出的 dp[j] + 1比dp[i] 更大的时候，才会更新。

比如上面的例子， j遍历到 1的时候，1 4是递增子序列，算出来的dp[3] + 1 = 2。

而并没有当时的dp[4] = 4更大，自然就不更新。

遍历顺序

正序遍历，内层for循环卡哥说也可以倒序遍历。

初始化

每个元素都是 1

Arrays.fill(dp, 1);

因为每个元素自己一定是一个递增子序列，就算只有自己，长度也是 1 呢。

实现中的困难

result 初始化应该是 1，因为至少答案也是 1.

感悟

学了新东西了

代码

这里打印dp数组的代码会导致超时

class Solution {
    public int lengthOfLIS(int[] nums) {
        //dp
        int[] dp = new int[nums.length];
        //init
        Arrays.fill(dp, 1);
        //function
        int result = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    result = Math.max(result, dp[i]);
                }
            }
            //print
            for (int k = 0; k < dp.length; k++) {
                System.out.print(dp[k]);
            }
            System.out.println();
        } 
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

674. 最长连续递增序列

本题相对于昨天的动态规划：300.最长递增子序列 最大的区别在于“连续”。 先尝试自己做做，感受一下区别
视频讲解：https://www.bilibili.com/video/BV1bD4y1778v
https://programmercarl.com/0674.%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E9%80%92%E5%A2%9E%E5%BA%8F%E5%88%97.html

第一印象

我自己试试这个连续的区别在哪了。

首先dp数组的含义应该是没变的

dp

都是 以 nums[i] 为结尾的子序列（包含它）的最长连续递增序列长度是 dp[i] 。

状态转移公式

既然必须连续，那么 i 只需要和 i - 1比较大小，要是 i 更大的话，dp[i] = dp[i - 1] + 1就可以了。
不需要跟0～i-2 这里面的元素比较了。

遍历顺序

正需便利

初始化

和上一道题一样都是 1.

看完题解的思路

我直接做出来了！！！

实现中的困难

没有

感悟

这道题比上一道题更简单了感觉。

代码

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        //dp
        int[] dp = new int[nums.length];
        int result = 1;
        //init
        Arrays.fill(dp, 1);
        //function
        for (int i = 1; i < dp.length; i++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
                result = Math.max(result, dp[i]);
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

第一印象

第一眼感觉和上面的题没啥关系

我自己试试

想不出来和不同的状态，看题解

看完题解思路

这道题感觉相当有难度哈哈哈哈 我看一遍视频都没怎么理解。

主要不理解dp[i][j] 是以i-1 为结尾和 j-1 为结尾的元素，最长的子序列。

我理解i-1 和j-1的事情，但不怎么理解这个二维数组的意义。

模拟一下实现过程吧。

过程大概理解了，但也没完全明白透。

dp数组

dp[i][j] 代表 nums1 中以 i - 1为结尾，nums2 中以 j - 1为结尾时，重复子串的最长长度。

这里的i-1和j-1 是为了初始化的时候更方便。所以遍历自然也要从i=1 j=1开始。

递推公式

这里的重复子串肯定是连续的子串，才叫公共子串，要是1 3 5和 1 4 3 5，重复子串就是 35 而不是 135.

只有两个元素相同的时候，才会让重复子串的长度+1.

思路是nums1 里拿一个 i ，nums2里拿一个 j，如果两个元素相同，说明出现重复的元素。

长度就应该 + 1，但是基于谁的长度呢？

就是基于i - 1和j - 1的。也就是不拿这个i 和不拿这个 j 的情况。

但并不是从头到尾遍历一遍就行了，因为1 2 3 2 1和 3 2 1 4 7的例子，重复的部分是从nums1[2] 和 nums2[0] 开始的。如果只是从头到后面遍历一次的话，就抓不到这样的重复情况了。

应该是两层for循环

for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
1
2

这样就是拿来nums1 里的第一个元素，然后挨个比较nums2里的 j，如果有相同，那么这个位置的最长重复子串就是 1. dp[1][j] = dp[0][j-1] + 1 = 0 + 1 = 1

再拿来nums1里的 第二个元素，挨个比较nums2里的，如果有相同，那么这个位置就是基于
dp[1][j-1] + 1 的结果。就是看不拿这两个元素的话，那个情况下最长是多少

• 这个情况可能是 0 ，也就是在这之前还没重复过，就是0 + 1 = 1了
• 这个情况也可能是 一个数字，比如2，也就是在这之前，已经有是连续重复的子串长度为 2 了。那么现在就是 2 + 1 = 3 这么长了。

遍历顺序

两层for循环里外都行，然后正序遍历

初始化

第一行第一列都应该是0 ，他们是非法的状态，但为了递推公式正确，应该是0

比如dp[1][1]就遇到重复元素了，dp[1][1] 应该是1。 而且递推公式的话 dp[1][1] = dp[0][0] + 1，所以都应该是 0.

实现中的困难

思路清晰的话实现没有什么问题

感悟

我觉得难在，怎么想的出这个是dp问题呢？

其次难在这个dp数组，因为要对两个数组进行操作，感觉是300.最长递增子序列的拓展。

两个数组就是二维的了那种感觉，每个元素都是一种情况。

代码

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        //dp
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        //init
        for (int j = 0; j < nums2.length + 1; j++) {
            dp[0][j] = 0;
        }
        for (int i = 0; i < nums1.length + 1; i++) {
            dp[i][0] = 0;
        }
        //func
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = result > dp[i][j] ? result : dp[i][j];
                }
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24