动态规划从入门到进阶：状态设计与空间优化的完整方法论

动态规划（Dynamic Programming，DP）是算法面试中区分度最高的主题。很多人觉得难，是因为把 DP 当成了"背套路"——但 DP 的本质只有四个字：重复子问题。本文用 Go 语言从"暴力递归 → 记忆化 → 递推"的演进路径讲透 DP 的推导方法，再覆盖背包、区间、状态压缩等进阶模型。

一、从斐波那契看懂 DP 的三个阶段

斐波那契数列的朴素递归：

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

计算 fib(50) 会慢到无法忍受，因为 fib(n-1) 和 fib(n-2) 各自递归时重复计算了大量相同子问题——这就是重叠子问题。

阶段一：记忆化搜索。把算过的结果存进缓存：

func fibMemo(n int, memo []int) int {
    if n <= 1 {
        return n
    }
    if memo[n] != 0 {
        return memo[n]
    }
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]
}

阶段二：自底向上递推。把递归改写成循环，从最小子问题一路推到目标：

func fibDP(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

阶段三：滚动数组优化。观察转移方程 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，空间从 O(n) 降到 O(1)：

func fibO1(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

这三步就是所有 DP 问题的通用路径：先暴力，再缓存，再递推，最后优化空间。

二、DP 题的标准解题四步法

1. 定义状态：dp[i] 代表什么？这是最关键的一步，状态定义决定了整个问题的走向；
2. 写出转移方程：dp[i] 怎么由更小的子问题推出来？把"最后一步"想清楚；
3. 确定边界条件：dp[0]、dp[1] 等初始值是什么；
4. 确定遍历顺序：保证计算 dp[i] 时依赖的子问题已经算好。

以"爬楼梯"为例：每次可以爬 1 或 2 阶，爬到第 n 阶有多少种方法？

• 状态：dp[i] = 爬到第 i 阶的方法数；
• 转移：dp[i] = dp[i-1] + dp[i-2]，因为最后一步要么从 i-1 跨 1 阶，要么从 i-2 跨 2 阶；
• 边界：dp[1]=1，dp[2]=2。

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    a, b := 1, 2
    for i := 3; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

LeetCode 70 与斐波那契同构——看出"同一类问题"是 DP 能力的分水岭。

三、经典模型一：0-1 背包

题目：n 件物品，第 i 件重量 w[i]、价值 v[i]，背包容量 W，每件只能取一次，求最大价值。

状态定义：dp[j] = 容量为 j 的背包能装下的最大价值。转移方程（一维滚动数组写法，注意 j 必须倒序遍历，避免同一件物品被取多次）：

func knapsack01(n, W int, w, v []int) int {
    dp := make([]int, W+1)
    for i := 0; i < n; i++ {
        for j := W; j >= w[i]; j-- {
            if dp[j-w[i]]+v[i] > dp[j] {
                dp[j] = dp[j-w[i]] + v[i]
            }
        }
    }
    return dp[W]
}

为什么倒序？因为一维数组复用后，正序遍历会让 dp[j-w[i]] 已经是"本轮更新过"的值，等价于同一件物品被取了多次——这正是完全背包想要的特性。

完全背包（每件可取无限次）只需把内层循环改成正序：

for j := w[i]; j <= W; j++ {
    if dp[j-w[i]]+v[i] > dp[j] {
        dp[j] = dp[j-w[i]] + v[i]
    }
}

多重背包（每件有限次）可以二进制拆分优化：把 k 件相同物品拆成 1、2、4、... 的若干"捆绑物品"，转化为 0-1 背包，把复杂度从 O(n×k×W) 降到 O(n×logk×W)。

四、经典模型二：区间 DP

状态定义里有两个维度且代表区间 [i, j] 的 DP，典型如"最长回文子序列"：

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }
    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else {
                if dp[i+1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i+1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[0][n-1]
}

注意区间 DP 的遍历顺序：按区间长度从小往大枚举，因为计算 dp[i][j] 依赖更短的区间 dp[i+1][j]、dp[i][j-1]。

五、经典模型三：状态压缩 DP

当状态维度很多但取值只有 0/1 时（比如"哪些城市已经访问过"），可以用二进制位表示状态。经典题"最短 Hamilton 路径"：

const INF = 1 << 30

func shortestHamilton(n int, g [][]int) int {
    // dp[S][i]: 已访问集合为 S，当前在城市 i 的最短路径
    dp := make([][]int, 1<<n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = INF
        }
    }
    dp[1][0] = 0
    for S := 1; S < 1<<n; S++ {
        for i := 0; i < n; i++ {
            if S>>i&1 == 0 {
                continue
            }
            for j := 0; j < n; j++ {
                if S>>j&1 == 1 || i == j {
                    continue
                }
                ns := S | 1<<j
                if dp[S][i]+g[i][j] < dp[ns][j] {
                    dp[ns][j] = dp[S][i] + g[i][j]
                }
            }
        }
    }
    return dp[(1<<n)-1][n-1]
}

状态数 2^n×n，n 一般限制在 20 以内，这是状态压缩 DP 的典型规模。

六、DP 与贪心、分治的区别

| 方法 | 核心思想 | 何时失效 | | --- | --- | --- | | 贪心 | 每步选局部最优 | 局部最优不等于全局最优时（如背包，重量与价值不成比例） | | 分治 | 子问题相互独立 | 子问题重叠时（重复计算） | | DP | 记录并复用重叠子问题的解 | 子问题不重叠时（退化为分治） |

判断一道题能否用 DP，就看两个性质：最优子结构（全局最优解包含局部最优解）和重叠子问题（求解过程反复遇到相同的子问题）。贪心能解的题（如活动选择、哈夫曼编码）通常也可以 DP 解，但贪心更省空间时间；DP 能解的题贪心不一定能解。

七、进阶：树形 DP 与记忆化在实战中的价值

树形 DP 在"树上打家劫舍"类问题上很典型——每棵子树是一个子问题，自底向上合并。这类题目把 DP 与 DFS 结合，是面试深度考察的常客。

最后给一条实战心法：DP 题做不出来时，先写暴力递归，再逐步加缓存。记忆化搜索和递推的复杂度相同，但推导难度低一个量级——先用自顶向下的思路把转移想通，再改写成自底向上的循环，是绝大部分人最快的进阶路径。理解"状态、转移、边界"三要素 + 掌握背包、区间、状压、树形四大模型，DP 就从玄学变成了工程。