动态规划基础

动态规划（Dynamic Programming，简称 DP）是算法设计中最重要、也是最容易让人困惑的思想之一。它通过将复杂问题分解为相互重叠的子问题，并存储子问题的解来避免重复计算，从而大幅提高效率。

核心思想

什么是动态规划？

想象你在爬楼梯，每次可以爬 1 阶或 2 阶，问爬到第 n 阶有多少种方法。你可以这样思考：

• 要到达第 n 阶，最后一步要么从第 n-1 阶跨 1 阶上来，要么从第 n-2 阶跨 2 阶上来
• 所以到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数

这就是动态规划的精髓：找到一个递推关系，从已知状态推导未知状态。

动态规划与其他算法的区别

算法	核心特点	子问题关系
分治	大问题拆分为小问题，分别解决后合并	子问题相互独立
贪心	每一步选择局部最优，期望得到全局最优	不考虑子问题
动态规划	存储子问题的解，避免重复计算	子问题有重叠

动态规划的适用条件

1. 最优子结构

问题的最优解包含子问题的最优解。比如最短路径问题，从 A 到 C 的最短路径如果经过 B，那么 A 到 B 的部分也必须是最短路径。

2. 重叠子问题

子问题会被重复计算。如果子问题完全不重叠，那就是分治，不是动态规划。比如斐波那契数列，fib(5) 需要计算 fib(4) 和 fib(3)，而 fib(4) 又需要计算 fib(3)，这里 fib(3) 就是重叠子问题。

3. 无后效性（马尔可夫性）

这是一个容易被忽视但很重要的条件：一旦某个状态确定了，它后续的发展只与当前状态有关，与之前如何到达这个状态的路径无关。

比如爬楼梯问题，第 i 阶的方法数只取决于第 i-1 和 i-2 阶的方法数，不关心具体是走哪条路径到达这些阶的。

解题四步法

1. 定义状态：明确 dp[i] 代表什么含义
2. 推导状态转移方程：找出状态之间的数学关系
3. 确定初始条件和边界：确定 dp[0] 等基础情况
4. 确定计算顺序：确保计算当前状态时，依赖的状态已经计算完成

这个方法论适用于绝大多数动态规划问题。下面通过经典问题来实践这个方法。

经典入门问题

斐波那契数列

斐波那契数列是最简单的动态规划入门：$f(n) = f(n-1) + f(n-2)$，其中 $f(0) = 0, f(1) = 1$。

方法一：暴力递归（不推荐）

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

问题：时间复杂度 $O(2^n)$，存在大量重复计算。比如计算 fib(5) 时，fib(3) 会被计算两次。

方法二：带备忘录的递归（自顶向下）

private int[] memo;  // 备忘录

public int fib(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return fibHelper(n);
}

private int fibHelper(int n) {
    if (n <= 1) return n;
    
    // 如果已经计算过，直接返回
    if (memo[n] != -1) return memo[n];
    
    // 计算并存储
    memo[n] = fibHelper(n - 1) + fibHelper(n - 2);
    return memo[n];
}

改进：时间复杂度降为 $O(n)$，每个子问题只计算一次。

方法三：迭代（自底向上）

public int fib(int n) {
    if (n <= 1) return n;
    
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

方法四：空间优化

由于 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，可以用两个变量替代数组：

public int fib(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;  // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

复杂度对比：

方法	时间复杂度	空间复杂度
暴力递归	$O(2^n)$	$O(n)$（递归栈）
备忘录递归	$O(n)$	$O(n)$
迭代	$O(n)$	$O(n)$
空间优化	$O(n)$	$O(1)$

爬楼梯（LeetCode 70）

每次可以爬 1 阶或 2 阶，问爬到第 n 阶有多少种方法。

分析：这与斐波那契完全相同，只是初始值不同。设 dp[i] 为爬到第 i 阶的方法数：

• 最后一步可以是 1 阶（从 i-1 上来）
• 最后一步可以是 2 阶（从 i-2 上来）
• 所以 dp[i] = dp[i-1] + dp[i-2]

初始条件：dp[1] = 1（爬 1 阶），dp[2] = 2（1+1 或 2）

public int climbStairs(int n) {
    if (n <= 2) return n;
    
    int prev2 = 1, prev1 = 2;  // dp[1], dp[2]
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

变体：如果每次可以爬 1 阶、2 阶或 3 阶呢？

状态转移方程变成 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

使用最小花费爬楼梯（LeetCode 746）

给定一个数组 cost，cost[i] 是从第 i 个台阶向上爬的费用。可以选择从索引 0 或 1 开始，求到达顶部的最小花费。

状态定义：dp[i] 表示到达第 i 个台阶的最小花费。

状态转移：可以从 i-1 或 i-2 跳上来： $dp[i] = \min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])$

初始条件：dp[0] = 0, dp[1] = 0（可以选择从 0 或 1 开始，开始时不需要花费）

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int prev2 = 0, prev1 = 0;  // dp[0], dp[1]
    
    for (int i = 2; i <= n; i++) {
        int curr = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

打家劫舍（LeetCode 198）

给定一个数组表示每间房子的金额，相邻的房子不能同时被抢，求能抢到的最大金额。

状态定义：dp[i] 表示考虑前 i 间房子能抢到的最大金额。

状态转移：对于第 i 间房子（索引为 i-1），有两种选择：

• 抢：nums[i-1] + dp[i-2]（不能抢第 i-1 间）
• 不抢：dp[i-1]

$dp[i] = \max(dp[i-1], dp[i-2] + nums[i-1])$

初始条件：dp[0] = 0, dp[1] = nums[0]

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

打家劫舍 II（LeetCode 213）

房子围成一圈，第一间和最后一间相邻。

解决思路：把问题拆成两个子问题

• 抢第一间，不抢最后一间：考虑 nums[0..n-2]
• 不抢第一间，可以抢最后一间：考虑 nums[1..n-1]

取两种情况的最大值。

public int rob2(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    if (n == 2) return Math.max(nums[0], nums[1]);
    
    // 情况1：抢第一间，范围[0, n-2]
    int case1 = robRange(nums, 0, n - 2);
    // 情况2：不抢第一间，范围[1, n-1]
    int case2 = robRange(nums, 1, n - 1);
    
    return Math.max(case1, case2);
}

private int robRange(int[] nums, int start, int end) {
    int prev2 = 0;
    int prev1 = nums[start];
    
    for (int i = start + 1; i <= end; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

动态规划问题分类

按状态维度分类

类型	状态定义	典型问题
一维 DP	dp[i] 表示以 i 结尾/前 i 个元素的最优解	斐波那契、打家劫舍、最大子数组和
二维 DP	dp[i][j] 表示两个序列或区间的最优解	LCS、编辑距离、矩阵路径
区间 DP	dp[i][j] 表示区间 [i,j] 的最优解	回文串、矩阵链乘法
状态压缩 DP	用二进制表示状态	旅行商问题、集合覆盖

按问题类型分类

问题类型	特点	典型问题
计数型	求方案数	爬楼梯、不同路径
最值型	求最大/最小值	打家劫舍、零钱兑换
存在性	判断是否可行	单词拆分、跳跃游戏

解题技巧

如何判断一道题用动态规划？

1. 问题求最值或方案数：这是动态规划最常见的信号
2. 问题可以分解为子问题：大问题的解依赖小问题的解
3. 子问题有重叠：暴力递归会有大量重复计算
4. 满足无后效性：当前状态确定后，未来发展只与当前状态有关

常见状态定义模式

问题类型	状态定义模式
序列问题	dp[i] 表示以 nums[i] 结尾的最优解
子序列问题	dp[i] 表示前 i 个元素的最优解
双序列问题	dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的最优解
区间问题	dp[i][j] 表示区间 [i,j] 的最优解
背包问题	dp[i][j] 表示前 i 个物品容量 j 的最优解

空间优化技巧

1. 滚动数组：如果 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，可以用变量代替数组
2. 状态压缩：如果状态可以用二进制表示（如集合），可以用位运算压缩
3. 逆序遍历：背包问题中，一维数组需要逆序遍历避免重复选择

练习题

入门：

1. LeetCode 70：爬楼梯
2. LeetCode 746：使用最小花费爬楼梯
3. LeetCode 509：斐波那契数

一维 DP： 4. LeetCode 198：打家劫舍 5. LeetCode 213：打家劫舍 II 6. LeetCode 337：打家劫舍 III（树形 DP） 7. LeetCode 322：零钱兑换 8. LeetCode 518：零钱兑换 II

二维 DP： 9. LeetCode 1143：最长公共子序列 10. LeetCode 72：编辑距离 11. LeetCode 62：不同路径 12. LeetCode 64：最小路径和

区间 DP： 13. LeetCode 5：最长回文子串 14. LeetCode 516：最长回文子序列