十大经典动态规划题（Go · ACM 模式）

💡 一句话概述

精选 10 道由易到难的 LeetCode 经典动态规划题，每道题重点讲解**状态定义、状态转移方程和 base case**，并给出完整的 Go ACM 模式（可编译运行的含 main 输入输出）题解。

---

🔑 核心概念

1. 状态（dp 含义） — DP 的第一步：明确 dp[i] / dp[i][j] 代表什么，定义清楚才能写出转移方程
2. 转移方程 — 用子问题递推当前问题，是 DP 的灵魂；从"最后一步"倒推最容易写对
3. base case（边界） — 递推的起跑线，通常是 i=0、空串、对角线等最小子问题
4. 遍历顺序 — 一维从左到右；二维按行；区间按长度；背包注意 0/1 逆序 vs 完全背包顺序
5. 滚动数组 / 状态压缩 — 当转移只依赖最近几行时，可由二维压成一维，降低空间复杂度

---

📝 详细说明

动态规划通用思考框架

拿到一道 DP 题，按以下 4 步走（全文每题都按这 4 步展开）：

1. 明确状态：dp[i] 表示"以第 i 个元素结尾 / 前 i 个元素"的答案是什么
2. 写出转移：考虑**最后一个动作**，把问题拆成更小的子问题（如爬到第 i 阶最后一步是 1 阶还是 2 阶）
3. 确定 base：dp[0]、dp[1] 或空串、边界行/列的值
4. 决定顺序：确保计算 dp[i] 时依赖的子问题（dp[i-1] 等）已经算好

10 题难度梯度总览

难度	题号	题目	DP 范式	核心转移方程
★	1	爬楼梯	一维线性	dp[i]=dp[i-1]+dp[i-2]
★	2	打家劫舍	一维 选/不选	dp[i]=max(dp[i-1],dp[i-2]+nums[i])
★★	3	最长递增子序列	一维序列	dp[i]=max(dp[j]+1)（nums[j]<nums[i]）
★★	4	不同路径	二维网格	dp[i][j]=dp[i-1][j]+dp[i][j-1]
★★	5	最长公共子序列	二维序列	相同 +1，不同取 max 左右
★★	6	分割等和子集	0/1 背包	逆序 dp[j] \|= dp[j-num]
★★★	7	完全平方数	完全背包	顺序 dp[j]=min(dp[j],dp[j-s]+1)
★★★	8	单词拆分	完全背包/匹配	dp[i] 由 dp[j]+子串命中推出
★★★	9	编辑距离	二维序列 三操作	增删替三者取 min
★★★	10	最长回文子序列	区间 DP	dp[i][j]=dp[i+1][j-1]+2

---

第 1 题：爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到楼顶。每次你可以爬 1 或 2 个台阶。问有多少种不同方法可以爬到楼顶？（LeetCode 70）

状态定义与转移

• 状态：f[i] 表示爬到第 i 阶的方法总数
• 转移：爬到第 i 阶，最后一步要么从 i-1 走 1 阶，要么从 i-2 走 2 阶，因此 f[i] = f[i-1] + f[i-2]
• base：f[0]=1（原地），f[1]=1

graph LR
    A["f[i-2]"] --> C["f[i] = f[i-1] + f[i-2]"]
    B["f[i-1]"] --> C

ACM 题解（Go）

package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)          // ACM 模式：读入 n
    if n <= 2 {
        fmt.Println(n)
        return
    }
    f := make([]int, n+1)
    f[1], f[2] = 1, 2
    for i := 3; i <= n; i++ {
        f[i] = f[i-1] + f[i-2]
    }
    fmt.Println(f[n])
}

---

第 2 题：打家劫舍

题目

你是一个专业小偷，沿街的房屋排成一排，相邻房屋连着保安。给定每个房屋的金额 nums[i]，求**不偷相邻两家**的前提下能偷到的最大金额。（LeetCode 198）

状态定义与 DP

• 状态：dp[i] 表示偷到前 i 间房子（下标 0..i）能得到的最大金额
• 转移：对第 i 间房，偷（nums[i] + 前 i-2 间最优）还是**不偷**（前 i-1 间最优），取大者： dp[i] = max(dp[i-1], dp[i-2] + nums[i])
• base：dp[0]=nums[0]，dp[1]=max(nums[0],nums[1])

graph LR
    A["dp[i-1] 不偷"] -.-> D{"max"}
    B["dp[i-2] + nums[i] 偷"] --> D
    D --> E["dp[i]"]

ACM 题解（Go）

package main

import (
    "bufio"
    "fmt"
    "os"
)

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    var n int
    fmt.Scan(&n)
    nums := make([]int, n)
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    for i := 0; i < n; i++ {
        sc.Scan()
        fmt.Sscan(sc.Text(), &nums[i])
    }
    if n == 0 {
        fmt.Println(0)
        return
    }
    if n == 1 {
        fmt.Println(nums[0])
        return
    }
    dp := make([]int, n)
    dp[0], dp[1] = nums[0], max(nums[0], nums[1])
    for i := 2; i < n; i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    }
    fmt.Println(dp[n-1])
}

---

第 3 题：最长递增子序列（LIS）

题目说明

给整数数组 nums，求**最长严格递增**的子序列（子序列可不连续，但要保持原顺序）的长度。（LeetCode 300）

思路与转移

• 状态：dp[i] 表示**以 nums[i] 结尾**的最长递增子序列长度
• 转移：从左往右枚举 j < i，若 nums[j] < nums[i]，则 nums[i] 可接到以 nums[j] 结尾的子序列后面，故 dp[i] = max(dp[i], dp[j] + 1)
• base：每个元素单独成序列，dp[i] 初始为 1

graph TD
    A["i-th 元素"] --> B{"有 j<i 且 nums[j]<nums[i] ?"}
    B -->|是| C["dp[i] = max(dp[i], dp[j]+1)"]
    B -->|否| D["dp[i] = 1"]

ACM 题解（Go）

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    var n int
    fmt.Scan(&n)
    nums := make([]int, n)
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    for i := 0; i < n; i++ {
        sc.Scan()
        fmt.Sscan(sc.Text(), &nums[i])
    }
    dp := make([]int, n)
    ans := 0
    for i := 0; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
            }
        }
        if dp[i] > ans {
            ans = dp[i]
        }
    }
    fmt.Println(ans)
}

O(n log n) 优化

用贪心+二分维护"长度为 len 的最小末尾"，可将 LIS 优化到 O(n log n)，但上面的 O(n²) 已能直观体现 dp 精髓，适合入门。

---

第 4 题：不同路径

题目说明

机器人在 m × n 网格左上角，每次只能**向右或向下**走一格，问到达右下角有多少条不同路径？（LeetCode 62）

状态定义与转移

• 状态：dp[i][j] 表示从左上角走到 (i,j) 的路径条数
• 转移：到达 (i,j) 只能从左边的 (i,j-1) 或上边的 (i-1,j) 过来，故 dp[i][j] = dp[i-1][j] + dp[i][j-1]
• base：第一行只能一路向右、第一列只能一路向下，故均为 1

graph TD
    A["(i-1,j) 从上"] --> B["dp[i][j]"]
    C["(i,j-1) 从左"] --> B
    B --> D["dp[i][j] = dp[i-1][j] + dp[i][j-1]"]

ACM 题解（Go）

package main

import "fmt"

func main() {
    var m, n int
    fmt.Scan(&m, &n)
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    fmt.Println(dp[m-1][n-1])
}

---

第 5 题：最长公共子序列（LCS）

题目说明

给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。子序列可以不连续。（LeetCode 1143）

二维表转移

• 状态：dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列长度
• 转移：
• 若 text1[i-1] == text2[j-1]：可拼在当前匹配字符，dp[i][j] = dp[i-1][j-1] + 1
• 否则取各自少一个字符中的较大者：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• base：dp[0][*]=dp[*][0]=0（空串与任何串的 LCS 为 0）

graph TD
    A{"text1[i-1] == text2[j-1] ?"}
    A -->|==| B["dp[i][j] = dp[i-1][j-1] + 1"]
    A -->|!=| C["dp[i][j] = max(dp[i-1][j], dp[i][j-1])"]

ACM 题解（Go）

package main

import (
    "bufio"
    "fmt"
    "os"
)

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    var a, b string
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    a = sc.Text()
    sc.Scan()
    b = sc.Text()
    m, n := len(a), len(b)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    fmt.Println(dp[m][n])
}

---

第 6 题：分割等和子集

题目条件

给定**非空**正整数数组 nums，判断能否把它分割成**两个元素和相等的子集**，即能否选出若干个数之和等于总和的一半。（LeetCode 416）

转化为 0/1 背包

sum 为奇直接不可能。目标 target = sum/2。这就是一个容量为 target 的 0/1 背包问题：每个数只能取一次，问能否恰好凑出 target。

• 状态：dp[j] 表示能否选出若干个数之和恰好等于 j
• 转移：对每个 num，若 dp[j-num]==true 则 dp[j] 可为 true，故 dp[j] = dp[j] || dp[j - num]
• 关键：背包**逆序遍历** j，保证 num 不会被重复使用（0/1 背包特性）
• base：dp[0]=true

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    var n int
    fmt.Scan(&n)
    nums := make([]int, n)
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sum := 0
    for i := 0; i < n; i++ {
        sc.Scan()
        fmt.Sscan(sc.Text(), &nums[i])
        sum += nums[i]
    }
    if sum%2 == 1 {
        fmt.Println("NO")
        return
    }
    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true
    for _, num := range nums {
        for j := target; j >= num; j-- { // 必须逆序：0/1 背包，一个数只能用一次
            if dp[j-num] {
                dp[j] = true
            }
        }
    }
    if dp[target] {
        fmt.Println("YES")
    } else {
        fmt.Println("NO")
    }
}

---

第 7 题：完全平方数

题目描述：给定正整数 n，求**最少数量的完全平方数**（如 1,4,9,16...）使其和为 n。（LeetCode 279）

这本质是一个**完全背包**（每种平方数可以重复取）求最小个数：

• 状态：dp[j] 表示凑出 j 所需的最少完全平方数个数
• 转移（加入一个平方数 s）：dp[j] = min(dp[j], dp[j-s] + 1)
• 注意这是**完全背包**：j **顺序**遍历，允许重复取同一个平方数
• base：dp[0]=0，其余初始化为无穷大

package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)
    const INF = 1 << 30
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = INF
    }
    dp[0] = 0
    for s := 1; s*s <= n; s++ { // 物品：完全平方数 s^2
        sq := s * s
        for j := sq; j <= n; j++ { // 顺序：完全背包，可重复取
            if dp[j-sq]+1 < dp[j] {
                dp[j] = dp[j-sq] + 1
            }
        }
    }
    fmt.Println(dp[n])
}

---

第 8 题：单词拆分

题目描述：给定字符串 s 和一个字典 wordDict，判断 s 是否可以被空格拆分成字典中一个或多个单词。（LeetCode 139）

• 状态：dp[i] 表示 s 的前 i 个字符能否被成功拆分
• 转移：若存在 j < i 使得 dp[j]==true 且区间 s[j:i] 是一个字典单词，则 dp[i]=true 即 dp[i] = dp[j] && s[j:i] ∈ wordDict（只要任一个 j 成立即可）
• base：dp[0]=true（空串可拆分）

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    var n int
    var s string
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    s = sc.Text()
    sc.Scan()
    fmt.Sscan(sc.Text(), &n)
    words := make(map[string]bool)
    for i := 0; i < n; i++ {
        sc.Scan()
        words[sc.Text()] = true
    }
    m := len(s)
    dp := make([]bool, m+1)
    dp[0] = true
    for i := 1; i <= m; i++ {
        for j := 0; j < i; j++ {
            if dp[j] && words[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    if dp[m] {
        fmt.Println("YES")
    } else {
        fmt.Println("NO")
    }
}

---

第 9 题：编辑距离

题目描述：给定两个字符串 word1 和 word2，通过对 word1 进行以下三种操作——插入、删除、替换一个字符——求把 word1 变成 word2 的**最少操作数**。（LeetCode 72）

• 状态：dp[i][j] 表示把 word1[0:i] 变成 word2[0:j] 的最少步数
• 转移（看 word1[i-1] 与 word2[j-1]）：
• 相同：dp[i][j] = dp[i-1][j-1]（不用动）
• 不同：取三者的最小值加 1
  • 删除 word1[i-1]：dp[i-1][j] + 1
  • 插入 word2[j-1]：dp[i][j-1] + 1
  • 替换：dp[i-1][j-1] + 1
• base：dp[i][0]=i（全删），dp[0][j]=j（全插）

package main

import (
    "bufio"
    "fmt"
    "os"
)

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    var w1, w2 string
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    w1 = sc.Text()
    sc.Scan()
    w2 = sc.Text()
    m, n := len(w1), len(w2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            c := dp[i-1][j-1] // 替换的代价（若字符相等则 0）
            if w1[i-1] == w2[j-1] {
                dp[i][j] = dp[i-1][j-1]
                continue
            }
            dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), c+1)
        }
    }
    fmt.Println(dp[m][n])
}

---

第 10 题：最长回文子序列

题目描述：给定字符串 s，找到其中最长的回文子序列的长度（子序列可不连续）。例如 bbbab → bbbb 长度为 4。（LeetCode 516）

• 状态：dp[i][j] 表示子串 s[i:j+1] 内的最长回文子序列长度
• 转移（两端字符比较）：
• 若 s[i]==s[j]：dp[i][j] = dp[i+1][j-1] + 2（两端都能加进回文）
• 若不同：dp[i][j] = max(dp[i+1][j], dp[i][j-1])（只能从两边去掉一个端）
• base：dp[i][i]=1（单个字符是回文）
• 遍历顺序：区间 DP 要**按区间长度从小到大**计算，保证 dp[i+1][j-1] 等更短区间已求出

package main

import (
    "bufio"
    "fmt"
    "os"
)

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    var s string
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    s = sc.Text()
    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] {
                if i+1 <= j-1 {
                    dp[i][j] = dp[i+1][j-1] + 2
                } else {
                    dp[i][j] = 2
                }
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            }
        }
    }
    fmt.Println(dp[0][n-1])
}

---

⚠️ 常见陷阱

0/1 背包 vs 完全背包的遍历顺序

分割等和子集（每个数只能用一次）必须**逆序**遍历 j；完全平方数（每个数可重复）必须**顺序**遍历 j。弄反了会导致重复计数或漏算，结果完全错误。

区间 DP 的遍历方向

第 10 题 dp[i][j] 依赖更短的 dp[i+1][j-1]，所以必须**按区间长度 level** 从小到大枚举，而不是简单地 i 从 0 到 n。

LIS 子序列 vs 子数组

dp[i] 定义成"以 nums[i] 结尾"，答案应是所有 dp[i] 取 max，而不是直接 dp[n-1]。求最长递增**子数组**（连续）时才看 dp[n-1]。

编辑距离的相等的 case

当 word1[i-1]==word2[j-1] 时直接继承 dp[i-1][j-1]，不要额外 +1，否则会把"本来不用改"的情况误算成替换。

---

🏋️ 练习题

练习 1：LeetCode 746 — 最小花费爬楼梯

数组 cost 表示每阶楼梯往上爬的开销，可以从第 0 或第 1 阶开始，每步能走 1 或 2 阶，到顶（越过数组末尾）最少花费多少？请用 dp 写出转移方程。

答案

状态 dp[i] 表示到达第 i 阶的最小花费，因为可以从 i-1（花 cost[i-1]）或 i-2（花 cost[i-2]）到达，因此 dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])，最终取 min(dp[n], dp[n-1])。

练习 2：LeetCode 322 — 零钱兑换

给定不同面额硬币 coins 和总金额 amount，问凑成 amount 至少需要多少枚硬币。它和第 7 题完全平方数有什么关系？可以仿照完全背包写出吗？

答案

类似，dp[j] = min(dp[j], dp[j-coin]+1)，且 coin 可重复使用，因此顺序遍历。与第 7 题唯一区别是物品从"平方数"换成"硬币面额"，解法完全一致。

练习 3：LeetCode 5 — 最长回文子串（子串 vs 子序列）

第 10 题求的是**子序列**。如果改成**连续的子串**，状态和转移哪里有区别？请说明并改 dp。

思路

子串要求连续，dp[i][j] 表示 s[i:j+1] 是否回文，转移为：s[i]==s[j] 且 j-i<=1 或 dp[i+1][j-1]。需要**记住最长长度**的起点和结束。子串具有"连续性"，子序列则可跳跃，这是关键差别。

---

🔗 相关链接

• LeetCode 70. 爬楼梯 — 一维斐波那契入门
• LeetCode 198. 打家劫舍 — 一维选/不选
• LeetCode 300. 最长递增子序列 — 序列 DP
• LeetCode 62. 不同路径 — 网格 DP
• LeetCode 1143. 最长公共子序列 — LCS
• LeetCode 416. 分割等和子集 — 0/1 背包
• LeetCode 279. 完全平方数 — 完全背包
• LeetCode 139. 单词拆分 — 背包式匹配
• LeetCode 72. 编辑距离 — 三操作二维
• LeetCode 516. 最长回文子序列 — 区间 DP