Demension

世界映射到我的维度

0%

leetcode-动态规划-1

发表于 更新于 分类于
本文字数： 6.8k 阅读时长 ≈ 6 分钟

动态规划

动态规划精讲1-题目列表

问题的特点

  • 最优子结构：原问题的最优解可以通过子问题的最优解推出。一般使用状态转移方程描述子问题之间、子问题和原问题之间的转化关系。
  • 重复子问题：求解不同子问题时需要进行大量相同的运算。动态规划中可采用记忆化递归或递推的方法减少重复问题的计算。如果子问题之间无重复，使用动态规划不能减少重复计算，效率和普通递归相同。

和其他算法的区别

分治

基本思想是减小子问题规模，分别求解子问题，然后综合子问题的解得出最终结果。分治法能够高效解决有最优子结构，但是没有重复子问题的问题。

贪心

动态规划 贪心
最优子结构 原问题最优解中一定包含某个子问题最优解，但不一定包含上一步子问题的最优解，因此需要记录之前所有子问题的最优解 每一步的最优解都一定包含上一步子问题的最优解，因此无需记录上一步之前的最优解
重复子问题 大量重复子问题 只要处理每步贪心策略选择出的一个子问题
结果正确性 动态规划的本质是穷举法（需要考虑所有子问题，但可以避免重复的计算），因此结果一定正确 求得的是贪心意义上的最优解，不能保证正确
算法复杂度 复杂度高 复杂度低

解题思路

线性动态规划

线性动态规划的主要特点是状态的推导是按照问题规模从小到大依次递推的，较大规模的问题的解依赖较小规模的问题的解。 线性动态规划解决的问题主要是单串，双串，矩阵上的问题，因为问题规模可以用位置表示，并且位置的大小就是问题规模的大小。因此从前往后推位置就相当于从小到大推问题规模。

最长上升子序列 / 最长递增子序列(LIS): Longest Increasing Subsequence 最长连续序列(LCS): Longest Consecutive Sequence 最长连续递增序列(LCIS): Longest Continuous Increasing Subsequence 最长公共子序列(LCS): Longest Common Subsequence

子串：一定连续 子序列：可以不连续

1
2
3
4
// 状态定义
dp[n] = [0, n]区间上问题的解
// 状态转移方程，由规模更小的状态转移而来
dp[n] = f(dp[n - 1], dp[n - 2], ..., dp[0])

线性DP-LIS

题目 难度 备注
300. 最长上升子序列 中等 单串-LIS
673. 最长递增子序列的个数 中等 单串-LIS扩展
354. 俄罗斯套娃信封问题 困难 单串-LIS｜排序
字节

最长上升子序列

状态定义： \(dp[i]\)表示以\(nums[i]\)结尾的最长上升子序列的长度。

状态转移： \[dp[i] = \left \{ \begin{aligned} s.t. \quad j \in [0, i - 1],\; nums[j] < nums[i] \\ max(dp[i],\; dp[j] + 1) \\ \end{aligned} \right.\]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    // TODO 分治
    // 方法 1
    // T = O(N^2), S = O(N)
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int len = nums.length;
        int max_len = 1;

        int[] dp = new int[len];
        Arrays.fill(dp, 1);

        for(int i = 1; i < len; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max_len = Math.max(max_len, dp[i]);
        }
        return max_len;
    }
}

最长递增子序列的个数

状态定义： \(dp[i]\)表示以\(nums[i]\)结尾的最长递增子序列的长度； \(count[i]\)表示以\(nums[i]\)结尾的最长递增子序列（长度相同）的组合个数。

转移方程： \[dp[i] = \left \{ \begin{aligned} s.t. \quad j \in [0, i - 1],\; nums[i] > nums[j] \\ max(dp[i],\; dp[j] + 1) \\ \end{aligned} \right.\] \[count[i] = \left \{ \begin{aligned} s.t. \quad j \in [0, i - 1],\; nums[i] > nums[j] \\ count[j] \quad dp[i] < dp[j] + 1 \\ sum(count[i],\; count[j]) \quad dp[i] = dp[j] + 1 \\ \end{aligned} \right.\]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int findNumberOfLIS(int[] nums) {
        if(nums == null || nums.length < 1){
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[len];
        int[] count = new int[len];
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        int max = 1;
        // 最长上升子串只需一层循环
        // 最长上升子序列则需要二重循环嵌套
        for(int i = 0; i < len; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    // 第一次找到以nums[i]结尾的LIS
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }
                    else if(dp[j] + 1 == dp[i]){
                        // 以nums[i]结尾的LIS已被找到过
                        count[i] += count[j];
                    }
                }
            }
            // 记录最长子序列的长度
            max = Math.max(max, dp[i]);
        }
        int res = 0;
        for(int i = 0; i < len; i++){
            if(dp[i] == max){
                res += count[i];
            }
        }
        return res;
    }
}

俄罗斯套娃信封问题

排序 + LIS，状态定义和转移方程同第300题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // T = O(N^2 + NlogN) = O(N^2), S = O(N)
        if(envelopes == null || envelopes.length == 0 || envelopes[0].length == 0){
            return 0;
        }
        int len = envelopes.length;

        Arrays.sort(envelopes, (o1, o2) -> {
            // 先按照宽度升序排序
            if(o1[0] != o2[0]){
                return o1[0] - o2[0];
            }
            else{
                // 如果宽度相同则按高度降序排序
                return o2[1] - o1[1];
            }
        });

        int res = 1;
        int[] dp = new int[len + 1];
        Arrays.fill(dp, 1);
        for(int i = 0; i < len; i++){
            for(int j = 0; j < i; j++){
                if(envelopes[i][1] > envelopes[j][1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

线性DP-最大子数组和

题目 难度 备注
53. 最大子序和 简单 最大子数组和
152. 乘积最大子数组 中等 最大子数组和
918. 环形子数组的最大和 中等 最大子数组和
面试题 17.24. 最大子矩阵 困难 最大子数组和-二维
363. 矩形区域不超过 K 的最大数值和 困难 最大子数组和

最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    // 方法1 贪心
    // T = O(n), S = O(1)
    public int maxSubArray_1(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int res = Integer.MIN_VALUE, tmp = 0;
        for(int num : nums){
            tmp += num;
            res = Math.max(res, tmp);
            tmp = tmp < 0 ? 0 : tmp;
        }
        return res;
    }

    // 方法 2 DP
    // T = O(N), S = O(N) -> O(1)
    public int maxSubArray_1(int[] nums) {
        // exception input
        int pre = 0, res = nums[0];
        for(int num : nums){
            pre = Math.max(pre + num, num);
            res = Math.max(res, pre);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    // 方法 3 线段树 + 分治
    // 可以方便地将所有运算以树的形式记忆化
    // 这样能够在O(logN)的时间复杂度下获取任意区间的最大子序和
    // T = O(logN), S = O(logN)

    // 自定义数据结构存储子区间状态
    class Status {
        public int lSum, rSum, mSum, iSum;
        public Status(int lSum, int rSum, int mSum, int iSum){
            this.lSum = lSum;   // 包含区间左端元素的最大子序和
            this.rSum = rSum;   // 包含区间右端元素的最大子序和
            this.mSum = mSum;   // 区间的最大子序和
            this.iSum = iSum;   // 区间所有元素和
        }
    }

    // 求指定区间内的状态信息
    public Status getInfo(int[] arr, int l, int r){
        if(l == r){
            return new Status(arr[l], arr[l], arr[l], arr[l]);
        }
        int mid = (l + r) / 2;
        Status lSub = getInfo(arr, l, mid);
        Status rSub = getInfo(arr, mid + 1, r);
        return pushUp(lSub, rSub);
    }

    // 将两个子区间的状态信息合并为更大区间的状态信息
    public Status pushUp(Status l, Status r){
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        int iSum = l.iSum + r.iSum;
        return new Status(lSum, rSum, mSum, iSum);
    }

    // 主函数
    public int maxSubArray(int[] nums) {
        // exception input
        return getInfo(nums, 0, nums.length - 1).mSum;
    }
}

乘积最大子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    // solution 4 
    public int maxProduct(int[] nums) {
        int res, max, min;
        res = max = min = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(nums[i] < 0){
                int tmp = max;
                max = min;
                min = tmp;
            }
            max = Math.max(max * nums[i], nums[i]);
            min = Math.min(min * nums[i], nums[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}

环形子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    // T = O(N), S = O(1)
    // 两次计算 1. 最大连续子数组和， 2. 最小连续子数组和
    public int maxSubarraySumCircular(int[] A) {
        int len = A.length;
        if(len == 1) return A[0];
        // maxSum 普通的最大连续子数组和
        // minSum 不包含数组首末元素的最小连续子数组和
        int sum = A[0], total = A[0], maxSum = A[0];
        for(int i = 1; i < len; i++){
            if(sum >= 0){
                sum += A[i];
            }
            else{
                sum = A[i];
            }
            maxSum = Math.max(sum, maxSum);
            total += A[i];
        }

        sum = A[1];
        int minSum = A[1];
        for(int i = 2; i < len - 1; i++){
            if(sum <= 0){
                sum += A[i];
            }
            else{
                sum = A[i];
            }
            minSum = Math.min(minSum, sum);
        }

        return Math.max(maxSum, total - minSum);
    }
}

最大子矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    // T = O(N^2), S = O(N)
    public int[] getMaxMatrix(int[][] matrix) {
        // exception input
        int row = matrix.length;
        int col = matrix[0].length;
        // 列方向压缩成一维数组
        int[] vector = new int[col];
        int[] res = new int[4];
        int maxSum = matrix[0][0];

        for(int i = 0; i < row; i++){
            for(int k = 0; k < col; k++) vector[k] = 0;

            for(int j = i; j < row; j++){
                for(int k = 0; k < col; k++) vector[k] += matrix[j][k];
                // 最大子串和(一维)
                int sum = 0;
                int start = 0;
                for(int c = 0; c < col; c++){
                    if(sum > 0){
                        sum += vector[c];
                    }
                    else{
                        sum = vector[c];
                        start = c;
                    }

                    if(sum > maxSum){
                        maxSum = sum;
                        res[0] = i;
                        res[1] = start;
                        res[2] = j;
                        res[3] = c;
                    }
                }
            }
        }

        return res;
    }
}

线性DP-打家劫舍

前缀和

区间动态规划

背包问题

状态压缩

计数问题

矩阵快速幂

数位动态规划

try 2

wow

try 3

wowow