核心思想

动态规划 = 把大问题拆成子问题 + 记住子问题的结果（记忆化/表格化）。关键在于找到「状态」和「状态转移方程」。

例1：爬楼梯

每次可爬 1 或 2 阶，到达第 n 阶有多少种走法？
状态：dp[i] = 到第 i 阶的方法数；转移：dp[i] = dp[i-1] + dp[i-2]

def climb(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

例2：0/1 背包

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]