算法训练营（day52）

动态规划理论基础

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

举个例子：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中 dp[j] 是由 dp[j-weight[i]] 推导出来的，然后取 max(dp[j], dp[j - weight[i]] + value[i])。

动态规划的解题步骤

  1. 确定 dp 数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp 数组如何初始化
  4. 确定遍历顺序
  5. 举例推导 dp 数组

300. 最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

解题思路

解题过程：动态规划

按照动规五部曲来分析：

  1. 确定dp数组（dp table）以及下标的含义

​ dp[j]表示容量为j的背包，最多可以背最大重量为dp[j]

​ 本题的 dp[i]：i之前包括i的以nums[i]结尾的最长递增子序列的长度

  1. 确定递推公式

    位置 i 的最长升序子序列等于 j 从0到 i-1 各个位置的最长升序子序列 + 1 的最大值。

​ 所以递推公式是：**dp[i] = max(dp[i], dp[j] + 1)**

  1. dp数组的初始化

    每一个 i，对应的 dp[i]（即最长递增子序列）起始大小至少都是1.

1
2
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
  1. 确定遍历顺序

​ dp[i] 是有0到 i-1 各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。

​ j 其实就是遍历0到 i-1 ，那么是从前到后，还是从后到前遍历都无所谓，只要 0 到 i-1 的元素都遍历就行。 所以默认习惯 从前向后遍历。

1
2
3
4
5
6
7
for(int i = 0; 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);
        }
    }
}
  1. 推导dp数组

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for(int i = 0; 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);
                }
            }
        }
        int res = 0;
        for(int i = 0; i < dp.length; i++){
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

674. 最长连续递增序列

题目链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

解题思路

解题过程：动态规划

按照动规五部曲来分析：

  1. 确定dp数组（dp table）以及下标的含义

​ dp[j]表示容量为j的背包，最多可以背最大重量为dp[j]

​ 本题的 dp[i]：以下标i为结尾的连续递增的子序列长度

  1. 确定递推公式

    如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以 i - 1为结尾的连续递增的子序列长度 + 1 。

​ 所以递推公式是：**dp[i] = dp[i - 1] + 1**

  1. dp数组的初始化

​ 初始的 dp 数组应该都初始化为 1，才能进行叠加

1
2
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
  1. 确定遍历顺序

​ 从递推公式上可以看出， dp[i] 依赖 dp[i - 1] ，所以一定是从前向后遍历。

1
2
3
4
5
6
for(int i = 1; i < dp.length; i++){
    if(nums[i - 1] < nums[i]){
        dp[i] = dp[i - 1] + 1;
    }
    res = Math.max(dp[i], res);
}
  1. 推导dp数组

详细代码

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

718. 最长重复子数组

题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

解题思路

解题过程：动态规划

按照动规五部曲来分析：

  1. 确定dp数组（dp table）以及下标的含义

​ dp[j]表示容量为j的背包，最多可以背最大重量为dp[j]

​ 本题的 dp[i]：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为 dp[i][j]。

特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串

  1. 确定递推公式

    根据 dp[i][j] 的定义，dp[i][j] 的状态只能由 dp[i - 1][j - 1] 推导出来。

    即当 A[i - 1] 和 B[j - 1] 相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1 ;根据递推公式可以看出，遍历i 和 j 要从1开始！

​ 所以递推公式是：**dp[i][j] = dp[i - 1][j - 1] + 1**

  1. dp数组的初始化

​ 根据上述定义，遍历i 和 j 从1开始，所以定义初始化是没有意义的，dp[i][j] 会根据递归公式直接从1开始计算，而 dp[0][0]则会被初始化为 0

  1. 确定遍历顺序

​ 外层for循环遍历A，内层for循环遍历B

​ 题目要求长度最长的子数组的长度。所以在遍历的时候顺便把 dp[i][j] 的最大值 res 记录下来

1
2
3
4
5
6
7
8
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;
        }
        res = Math.max(dp[i][j], res);
    }
}
  1. 推导dp数组

详细代码

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int res = 0;

        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;
                }
                res = Math.max(dp[i][j], res);
            }
        }
        return res;
    }
}

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length + 1];
        int res = 0;

        for(int i = 1; i <= nums1.length; i++){
            for(int j = nums2.length; j > 0; j--){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[j] = dp[j - 1] + 1;
                }else{
                    dp[j] = 0;
                }
                res = Math.max(dp[j], res);
            }
        }
        return res;
    }
}