动态规划基础

动态规划（Dynamic Programming，DP）通过把原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算，从而大幅提高效率。

核心思想

什么是动态规划？

动态规划的核心是将复杂问题分解为子问题，并存储子问题的解以避免重复计算。

与分治的区别：分治子问题相互独立；动态规划子问题有重叠。 与贪心的区别：贪心每步局部最优；动态规划考虑全局最优。

适用条件

1. 最优子结构：问题的最优解包含子问题的最优解。
2. 重叠子问题：子问题会被重复计算。
3. 无后效性：前面的状态一旦确定，不受后续决策影响。

解题步骤

1. 定义状态：明确 dp[i] 的含义。
2. 状态转移方程：找出状态之间的数学关系。
3. 初始化：确定边界条件（如 dp[0]）。
4. 计算顺序：确保计算当前状态时，依赖的状态已完成。

经典入门：斐波那契与爬楼梯

1. 斐波那契数列

// 动态规划 - O(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];
}

// 空间优化 - O(1) 空间
public int fibOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

2. 爬楼梯 (LeetCode 70)

每次爬 1 或 2 阶。到达第 $i$ 阶的方法数 = 到达第 $i-1$ 阶的方法数 + 到达第 $i-2$ 阶的方法数。

打家劫舍系列 (House Robber)

不能偷相邻的房子。

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 - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
}

练习

1. LeetCode 70：爬楼梯
2. LeetCode 198：打家劫舍
3. LeetCode 746：使用最小花费爬楼梯
4. LeetCode 509：斐波那契数