动态规划入门：记住算过的结果

这一课你将能做到

1. 说出动态规划两要素（最优子结构、重叠子问题）和解题四步（定义、转移、初值、遍历）
2. 用滚动变量写爬楼梯，用 0/1 背包模型解决分割等和子集
3. 写出最长递增子序列的 DP 解法，并推导出编辑距离的二维状态转移

为什么要学

动态规划（DP）是很多人心里的「终极大 BOSS」：听题解时醍醐灌顶，自己写无从下手。其实它只比递归多一个朴素动作——把算过的子问题结果存起来，下次直接取用。回溯之所以指数爆炸，是因为相同的子问题被算了成千上万遍；DP 用一张表消掉这些重复，常常把 O(2ⁿ) 直接压到 O(n²)。

DP 在工程里离你并不远：路径规划、文本比对（Git diff 就是编辑距离的变体）、资源分配、推荐系统的序列建模都有它的影子。作为收官课，本课用四道由浅入深的经典题帮你建立通用解题框架。能拿下这四题，LeetCode 中等难度的 DP 题你就具备了「读题拆状态」的基本能力。

先建立图像

先看递归的浪费与 DP 的节省（以爬楼梯为例，到第 n 阶）：

递归树：f(5)
        /        \
     f(4)        f(3)      ← f(3) 在整棵树里被反复计算
     /  \        /  \
  f(3) f(2)   f(2) f(1)
   ...大量重复...

DP：f(1)=1, f(2)=2 → f(3)=3 → f(4)=5 → f(5)=8
    每个子问题只算一次

解题四步法（每道 DP 题都按这个顺序想）：

1. 定义状态：dp[i]（或 dp[i][j]）到底表示什么？
2. 写转移方程：当前状态从哪些更早的状态来？
3. 定初始值与边界：最小的状态是多少？
4. 确定遍历顺序：保证算当前值时，依赖的值已经算好。

跟着做

步骤 1：LeetCode 70「爬楼梯」（简单）

每次可爬 1 或 2 阶，到第 n 阶共多少种走法。

定义 dp[i] = 到第 i 阶的走法数。到达第 i 阶的最后一步，要么从 i-1 跨 1 阶、要么从 i-2 跨 2 阶，两类互斥：dp[i] = dp[i-1] + dp[i-2]。

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

逐点讲：每次只依赖前两个值，用两个滚动变量即可，不必开数组。时间 O(n)，空间 O(1)。这题就是斐波那契模型，也是理解 DP 的第一块台阶。

步骤 2：LeetCode 416「分割等和子集」（中等，0/1 背包）

判断能否把数组分成两个和相等的子集。

转化：总和为 sum，问题等价于「能否选出若干数，恰好凑成 sum/2」——这正是 0/1 背包（每个数选或不选，只能用一次）。

定义 dp[j] = 能否（true/false）凑出和 j。对每个数 num，从目标容量倒序更新（倒序保证每个数只用一次）：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % 2 != 0) {
            return false; // 和为奇数，无法平分
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // 什么都不选，凑出 0
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num]; // 不选 / 选 num
            }
        }
        return dp[target];
    }
}