一、动态规划简介

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

1.1 三个基本概念

• 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构。
• 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
• 重复子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

1.2 动态规划组成部分

1. 确定状态
   • 研究最优策略的最后一步
   • 化为子问题
2. 转移方程
   • 根据子问题定义直接得到f(1), f(2), … f(n - 1)与f(n)的关系
3. 初始条件和边界情况
   • 细心，考虑周全
4. 计算顺序
   • 利用之前的计算结果

1.3 与其他算法的关系

	分治	动态规划	贪心
适用类型	通用	优化	优化
子问题	每个都不同	有很多重复	只有一个
最优子结构	没有要求	必须满足	必须满足
子问题数	全部都要解	全部都要解	只解一个

二、线性动态规划

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。

2.1 单串问题

最经典单串LIS问题

最长递增子序列⭐

⚡ 动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;

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

⚡ 贪心 & 二分⭐

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // id[i] 表示长度为i的递增子序列末尾最小值
        int[] id = new int[n + 1];
        int tt = 0;

        id[tt] = 0;
        for (int i = 0; i < n; ++i) {
            int l = 0, r = tt;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (id[mid] < nums[i]) l = mid;
                else  r = mid - 1;
            }
            id[r + 1] = nums[i];
            tt = Math.max(tt, r + 1);
        }
        return tt;
    }
}

最长递增子序列的个数

⚡ 动态规划

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] lengths = new int[n];//存以i号位置元素结尾的最长子序列
        int[] counts = new int[n];//以i位置元素结尾的最长子序列的数量

        for (int i = 0; i < n; ++i) {
            lengths[i] = 1; counts[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                   if (lengths[j] >= lengths[i]) {
                       lengths[i] = lengths[j] + 1;
                       counts[i] = counts[j];
                   }
                   else if (lengths[j] + 1 == lengths[i]) {
                       counts[i] += counts[j];
                   }
                }
            }
        }
        int longest = 0, count = 0;
        for (int len : lengths) {
            longest = Math.max(longest, len);
        }
        for (int i = 0; i < n; ++i) {
            if (lengths[i] == longest) {
                count += counts[i];
            }
        }
        return count;
    }
}

俄罗斯套娃信封问题🌟

⚡ 动态规划

class Solution {
    public int maxEnvelopes(int[][] envelopes) {

        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) return o1[0] - o2[0];
                else return o2[1] - o1[1];
            }
        });

        int n = envelopes.length;
        //dp[i]表示以i号信封结尾的组合中最大信封个数
        int[] dp = new int[n];
        int max = 0;
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

最大子数组和系列

最大子序和⭐（Kanade算法）

⚡ 动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ans = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            //dp[i]表示包括以i号数字结尾的字符串的最大值
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
}

⚡ 优化掉dp数组

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int lastNum = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; ++i) {
            lastNum = Math.max(lastNum + nums[i], nums[i]);
            ans = Math.max(lastNum, ans);
        }
        return ans;
    }
}

乘积最大子数组

⚡ 动态规划

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        //考虑正负数相乘，维护一个最大和一个最小的dp数组
        int[] maxDp = new int[n];
        int[] minDp = new int[n];
        maxDp[0] = nums[0];
        minDp[0] = nums[0];
        int ans = nums[0];

        for (int i = 1; i < n; ++i) {
            maxDp[i] = Math.max(maxDp[i - 1] * nums[i], Math.max(minDp[i - 1] * nums[i], nums[i]));
            minDp[i] = Math.min(minDp[i - 1] * nums[i], Math.min(maxDp[i - 1] * nums[i], nums[i]));
            ans = Math.max(ans, maxDp[i]);
        }
        return ans;
    }
}

⚡ 优化掉dp数组

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxP = nums[0];
        int minP = nums[0];
        int ans = nums[0];

        for (int i = 1; i < n; ++i) {
            int mx = maxP, mn = minP;
            maxP = Math.max(mx * nums[i], Math.max(mn * nums[i], nums[i]));
            minP = Math.min(mn * nums[i], Math.min(mx * nums[i], nums[i]));
            ans = Math.max(ans, maxP);
        }
        return ans;
    }
}

环形子数组的最大和⭐

⚡ 动态规划
若使用到了环，则最大子序列中必定包含A[n-1]和A[0]两个元素，且说明从A[1]到A[n-2]这个子数组中必定包含负数，否则只通过一趟最大子序和就可以得出结果。
因此只需要把A[1]-A[n-2]间这些负数的最小和求出来，用整个数组的和 sum减掉这个负数最小和即可实现原环型数组的最大和。最后再与无环子序列情况下得到最大和进行比较即可。

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int n = A.length;
        if (n == 1) return A[0];

        int[] dp = new int[n];
        dp[0] = A[0];
        int ansMax = dp[0]; //不使用环的情况下子数组的最大和
        int sum = A[0];

        for (int i = 1; i < n; ++i) {
            dp[i] = Math.max(dp[i - 1] + A[i], A[i]);
            ansMax = Math.max(ansMax, dp[i]);
            sum += A[i];
        }

        dp[1] = A[1];
        int ansMin = dp[1]; //使用环的情况下1到n-2内子数组的最小和
        for (int i = 2; i < n - 1; ++i) {
            dp[i] = Math.min(dp[i - 1] + A[i], A[i]);
            ansMin = Math.min(ansMin, dp[i]);
        }
        //sum - ansMin即为使用环的情况下的子数组最大和
        return Math.max(ansMax, (sum - ansMin));
    }
}

打家劫舍系列

打家劫舍

⚡ 动态规划

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
}

打家劫舍 II

见LeetCode每日打卡-April4月15日

股票系列

买卖股票的最佳时机

⚡ 单次遍历

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            ans = Math.max(ans, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return ans;
    }
}

买卖股票的最佳时机II

⚡ 动态规划

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n];
        dp[0] = 0;
        for (int i = 1; i < n; ++i) {
            //转移方程
            dp[i] = dp[i - 1] + Math.max(prices[i] - prices[i - 1], 0);
        }
        return dp[n - 1];
    }
}

⚡ 贪心

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i = 1; i < prices.length; ++i) {
            if(prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

其他问题

丑数II

见LeetCode每日打卡-April4月11日

直方图的水量⭐

见LeetCode每日打卡-April4月2日

跳跃游戏

⚡ 动态规划 Time: O(n2) Space: O(n)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 1; i < n; ++i) {
            dp[i] = false;
            for (int j = 0; j < i; ++j) {
                if(dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n - 1];
    }
}

⚡ 贪心 Time: O(n) Space: O(1)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int maxlen = 0;
        for (int i = 0; i < n; ++i) {
            if (maxlen >= i) {
                maxlen = Math.max(maxlen, nums[i] + i);
                if (maxlen >= n - 1) return true;
            }
        }
        return false;
    }
}

2.2 双串问题

最经典的双串LCS系列

最长公共子序列

⚡ 经典问题

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int dp[][] = new int[m+1][n+1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                //转移方程
                if (text1.charAt(i-1) == text2.charAt(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]);
            }
        }
        return dp[m][n];
    }
}

带维度的双串问题

扰乱字符串🌟

见LeetCode每日打卡-April4月16日

2.3 矩阵问题

三角形最小路径和

⚡ 动态规划

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int[][] dp = new int[m][m];
        dp[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < m; ++i) {
            dp[i][0] = triangle.get(i).get(0) + dp[i - 1][0];
            for (int j = 1; j < i; ++j) {
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
            }
            dp[i][i] = triangle.get(i).get(i) + dp[i - 1][i - 1];
        }

        int ans = dp[m - 1][0];
        for (int num : dp[m - 1]) {
            ans = Math.min(ans, num);
        }
        return ans;
    }
}

三、前缀和

3.1 实现前缀和问题

区域和检索-数组不可变

⚡ 检索时间复杂度O(1)

class NumArray {
    int[] sums;

    public NumArray(int[] nums) {
        int n = nums.length;
        //sums[i]表示nums前i-1项的和
        sums = new int[n + 1];
        sums[0] = 0;
        for (int i = 0; i < n; ++i) {
            sums[i + 1] = nums[i] + sums[i];
        }
    }

    public int sumRange(int left, int right) {
        return sums[right + 1] - sums[left];
    }
}

二维区域和检索-矩阵不可变

⚡ 检索时间复杂度O(1)

class NumMatrix {
    int[][] sumMatrix;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        sumMatrix = new int[m][n];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) {
                    sumMatrix[i][j] = matrix[i][j];
                }
                else if (i == 0) {
                    sumMatrix[i][j] = sumMatrix[i][j - 1] + matrix[i][j];
                }
                else if (j == 0) {
                    sumMatrix[i][j] = sumMatrix[i - 1][j] + matrix[i][j];
                }
                else {
                    int sumII = 0, sumJJ = 0;
                    for (int ii = 0; ii < i; ++ii) {
                        sumII += matrix[ii][j];
                    }
                    for (int jj = 0; jj < j; ++jj) {
                        sumJJ += matrix[i][jj];
                    }
                    sumMatrix[i][j] = sumMatrix[i - 1][j - 1] + sumII + sumJJ + matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = sumMatrix[row2][col2];

        if (row1 > 0) {
                sum -= sumMatrix[row1 - 1][col2];
            }
        if (col1 > 0) {
                sum -= sumMatrix[row2][col1 - 1];
        }
        if (row1 > 0 && col1 > 0) {
            sum += sumMatrix[row1 - 1][col1 - 1];
        }
        return sum;

    }
}

⚡ 代码优化

class NumMatrix {
    int[][] sums;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            sums = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
}

3.2 维护前缀和问题

和为K的子数组⭐

⚡ 暴力

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;

        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = i; j < n; ++j) {
                sum += nums[j];
                if (sum == k) ++count;
            }
        }
        return count;
    }
}

⚡ 动态规划 & 哈希表

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        int pre = 0;

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);

        for (int i = 0; i < n; ++i) {
            pre += nums[i];
            //仔细体会这里为什么是pre - k ⭐
            if (hashMap.containsKey(pre - k)) {
                count += hashMap.get(pre - k);
            }
            hashMap.put(pre, hashMap.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

和等于k的最长子数组长度

⚡ 动态规划 & 哈希表

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int n = nums.length;
        int max = 0, pre = 0;

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, -1);

        for (int i = 0; i < n; ++i) {
            pre += nums[i];
            max = Math.max(max, i - hashMap.getOrDefault(pre - k, i));
            //只记录第一次的位置
            if (!hashMap.containsKey(pre)) {
                hashMap.put(pre, i);
            }
        }
        return max;
    }
}

连续数组

⚡ 动态规划 & 哈希表

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int count = 0; //奇数和偶数之差

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, -1); //key为奇数和偶数的差

        for (int i = 0; i < n; ++i) {
            if (nums[i] % 2 == 0) --count;
            else ++count;

            if (hashMap.containsKey(count)){
                ans = Math.max(ans, i - hashMap.get(count));
            }
            else hashMap.put(count, i); 
        }
        return ans;
    }
}

func findMaxLength(nums []int) int {
    map_variable := map[int]int{
        0: -1,
    }

    count, maxLen := 0, 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            count += -1
        } else {
            count += 1
        }
        if v, ok := map_variable[count]; ok {
            maxLen = max(maxLen, i - v)
        } else {
            map_variable[count] = i
        }
    }
    return maxLen
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}

统计「优美子数组」

⚡ 动态规划 & 哈希表

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        //Key为奇数数量，Value为前缀和为Key数量
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        int ans = 0, sum = 0;

        for (int num : nums) {
            sum += num & 1;
            ans += hashMap.getOrDefault(sum - k, 0);
            hashMap.put(sum, hashMap.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

连续的子数组和

⚡ 动态规划 & 哈希表

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //理解初始化的含义
        hashMap.put(0, -1);
        int sum = 0;

        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            int modulus = sum % k;
            if (hashMap.containsKey(modulus)) {
                if (i - hashMap.get(modulus) > 1) return true;
            }
            else hashMap.put(modulus, i);
        }
        return false;
    }
}

和可被K整除的子数组

⚡ 动态规划 & 哈希表

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int n = A.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //体会初始化含义
        hashMap.put(0, 1);

        int sum = 0, ans = 0;
        for (int num : A) {
            sum += num;
            int modulus = (sum % K + K) % K; //当被除数为负数时取模结果为负数，需要纠正
            int same = hashMap.getOrDefault(modulus, 0);
            ans += same;
            hashMap.put(modulus, same + 1);
        }
        return ans;
    }
}

⚡ 数组代替哈希表

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int[] map = new int[k];
        map[0] = 1;
        int sum = 0, ans = 0;
        for (int num : nums) {
            sum += num;
            int idx = (sum % k + k) % k;
            ans += map[idx] ++;
        }
        return ans;
    }
}

四、区间动态规划

LeetCode题库–May 5.24 - 奇怪的打印机

五、背包动态规划

• 分析步骤
  1. 分析是否为背包问题。
  2. 是背包问题三种问法中的哪一种。
  3. 是 0-1 背包问题还是完全背包问题。也就是题目给的 nums 数组中的元素是否可以重复使用。
  4. 如果是组合问题，即求方案数，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法，需要注意。

5.1 最值问题

零钱兑换⭐

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        int n = coins.length;
        f[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            f[i] = Integer.MAX_VALUE;

            for (int j = 0; j < n; ++j) {
                if (i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE) {//边界情况
                    f[i] = Math.min(f[i - coins[j]] + 1, f[i]); //转移方程
                }
            }
        }
        if (f[amount] == Integer.MAX_VALUE) {
            f[amount] = -1;
        }
        return f[amount];
    }
}

5.2 组合问题（求方案数）

零钱兑换II⭐

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int x = coin; x <= amount; ++x) {
                dp[x] += dp[x - coin];
            }
        }
        return dp[amount];
    }
}

组合总和Ⅳ

⚡ 动态规划

class Solution {
    public int combinationSum4(int[] nums, int target) {
        //dp[i]表示组合为i的方案数
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; ++i) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}

六、状态压缩动态规划

七、计数问题

7.1 路径问题

不同路径⭐

⚡ 动态规划

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m-1][n-1];
    }
}

不同路径 II

⚡ 动态规划

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    if (i == 0 && j == 0) continue;
                    if (i == 0) {
                        dp[i][j] = dp[i][j - 1];
                    } else if (j == 0) {
                        dp[i][j] = dp[i - 1][j];
                    } else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

⚡ 滚动数组优化

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if(obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j >= 1) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}

7.2 斐波那契

青蛙跳台阶问题

⚡ 动态规划

class Solution {
    public int numWays(int n) {
        if(n <= 1) return 1;
        int[] dp = new int[n+1];
        dp[0] = 1; dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
}

⚡ 上面方法优化空间复杂度

class Solution {
    public int numWays(int n) {
        int a = 1, b = 1;
        int sum = 1;
        for (int i = 2; i <= n; ++i) {
            sum = (a + b) % 1000000007;
            b = a;
            a = sum;
        }
        return sum;
    }
}

八、矩阵快速幂

九、数位动态规划