【算法刷题】leetcode hot 100 动态规划

动态规划基础

动态规划（Dynamic Programming，简称 DP）是一种将复杂问题分解为子问题来解决的方法。它主要适用于满足以下两个条件的问题：

• 重叠子问题：原问题可以拆分为多个子问题，而这些子问题之间有很多重复计算。
• 最优子结构：问题的最优解可以由子问题的最优解构成。

举个简单的例子，斐波那契数列：

• 定义 F(n) = F(n-1) + F(n-2)（重叠子问题：F(n-1) 和 F(n-2) 可能重复计算）。
• 通过缓存中间结果（记忆化或自底向上迭代），可以避免重复计算。

动态规划的核心要素

设计 DP 解法通常需要确定三个部分：

• 状态定义
  确定用什么样的变量（数组、矩阵等）记录子问题的解。
  例如，在「最大子序和」问题中，我们可以定义 dp[i] 表示以第 i 个数结尾的连续子数组的最大和。
• 状态转移方程
  分析如何从子问题的解推出当前问题的解。
  例如，「最大子序和」的状态转移可以写作：
  dp[i] = max(nums[i], dp[i-1] + nums[i])
• 初始状态和边界条件
  根据问题设定初始值，例如 dp[0] = nums[0]；同时要注意边界情况。

一维动态规划实例

最大子序和（LeetCode 53）

问题描述：给定一个整数数组，求一个具有最大和的连续子数组。
状态定义：dp[i] 表示以第 i 个元素为结尾的连续子数组最大和。
状态转移：

• 当 dp[i-1] 是正数时，可以加上 nums[i]，否则直接选 nums[i]：
  dp[i] = max(nums[i], dp[i-1] + nums[i])

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

多维动态规划

当问题涉及二维（或更多维）的状态时，就需要用到多维 DP。常见场景有二维数组（矩阵）问题、字符串问题等。

矩阵类问题示例

不同路径（LeetCode 62）

问题描述：在一个 m×n 的网格中，从左上角出发，每次只能向下或向右移动，求到达右下角的不同路径数。
状态定义：dp[i][j] 表示从起点到坐标 (i, j) 的路径数。
状态转移：

• 当前位置的路径数等于上方和左边的路径数之和：
  dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 初始条件：第一行和第一列只有一条路径。

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // 第一行和第一列初始化为1
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        // 填充 DP 数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

最小路径和（LeetCode 64）

问题描述：在一个 m×n 的矩阵中，找到从左上角到右下角路径上的最小和，每次只能向下或向右移动。
状态转移：

• dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

字符串类问题示例

编辑距离（LeetCode 72）

问题描述：给定两个字符串，求将第一个字符串转换成第二个字符串的最小编辑距离。
状态定义：

• dp[i][j] 表示将字符串 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。
  状态转移：
• 如果最后一个字符相同：dp[i][j] = dp[i-1][j-1]
• 如果不同，则考虑替换、删除或插入操作： dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        // 初始化边界条件
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i-1][j-1], 
                                    Math.min(dp[i-1][j], dp[i][j-1]));
                }
            }
        }
        return dp[m][n];
    }
}

多维 DP 的设计思路

多维 DP 的设计和一维类似，但状态往往由多个维度构成。设计时需要注意以下几点：

1. 状态维度的选择
   根据问题需求确定需要记录哪些信息。比如：
   • 路径问题：二维坐标 (i, j)；
   • 字符串问题：两个字符串的下标 (i, j)；
   • 多状态问题：可能需要额外维度表示是否选取、当前容量等。
2. 转移顺序和边界处理
   多维 DP 数组的遍历顺序非常重要，通常需要保证转移时所依赖的子问题已经计算好。比如在矩阵问题中通常从左上角开始迭代。
3. 空间优化
   如果状态转移只依赖于前一行（或前一维），可以将二维 DP 数组降维为一维，从而减少空间占用。