动态规划入门：线性 DP、背包 DP 与区间 DP

面向第一次系统学习动态规划的读者。本文默认使用 Python 3。

目录

1. 先弄懂：动态规划到底是什么
2. 写 DP 的通用五步法
3. 线性 DP
4. 背包 DP
5. 区间 DP
6. 三类 DP 的区别与识别方法
7. 调试 DP 的实用方法
8. 学习路线与练习建议
9. 最终速查表

---

一、先弄懂：动态规划到底是什么

1. 从一个小问题开始

假设你要爬到第 n 级台阶，每次只能爬 1 级或 2 级，问一共有多少种爬法。

如果最后一步爬了 1 级，那么此前一定在第 n-1 级；如果最后一步爬了 2 级，那么此前一定在第 n-2 级。因此：

$$dp[n] = dp[n-1] + dp[n-2]$$

这里的 dp[i] 表示“爬到第 i 级台阶的方案数”。

这就是动态规划最核心的思想：

先保存小问题的答案，再利用这些答案推出更大问题的答案。

2. DP 通常解决什么问题

动态规划经常用来求以下三类答案：

• 最优值：最大价值、最小花费、最长长度、最少次数。
• 方案数：一共有多少种选择或路径。
• 可行性：能不能完成、某个状态是否可以到达。

例如：

最少需要分成几段？       -> 最小值 DP
容量有限时最大价值是多少？ -> 最大值 DP
有多少条合法路径？       -> 计数 DP
能否正好凑出某个金额？    -> 布尔 DP

3. 什么情况下可以考虑 DP

一道题具有下面的特征时，可以尝试动态规划：

1. 大问题能够拆成规模更小、形式相同的子问题。
2. 不同选择会反复遇到相同的子问题。
3. 当前问题的答案可以由已经解决的子问题推出来。

但“看见最大、最小就用 DP”是不对的。DP 最重要的是能定义出含义明确的状态，并找到无遗漏、无重复的转移。

4. DP 与贪心的区别

• 贪心：每一步只保留当前看起来最好的选择，希望它最终也是全局最优。
• DP：记录多个有用的中间状态，比较不同选择后得到全局最优。

如果无法证明“当前最优选择一定属于最终最优方案”，就不能轻易使用贪心。

---

二、写 DP 的通用五步法

无论是哪种 DP，都可以按下面五步思考。

第一步：定义状态

必须先用一句完整的话说清楚 dp[...] 的含义。

例如：

dp[i] 表示前 i 个元素的最优答案。
dp[i] 表示以第 i 个元素结尾的最长上升子序列长度。
dp[j] 表示容量不超过 j 时能够获得的最大价值。
dp[l][r] 表示处理区间 [l, r] 的最小代价。

状态定义中每一个词都很重要。“前 i 个”和“以 i 结尾”是不同的含义，会产生不同的转移。

第二步：寻找最后一步

不知道如何转移时，可以问：

要得到当前答案，最后一次选择是什么？在这次选择之前，问题变成了哪个更小的问题？

常见问法：

• 最后一段从哪里开始？
• 第 i 个物品选还是不选？
• 最后合并的是哪两个区间？
• 当前元素接在哪个元素后面？

第三步：写出转移方程

例如：

$$dp[i] = \min_{0 \le j < i}\{dp[j] + cost(j+1,i)\}$$

不要急着写代码。先用自然语言或数学公式说明“从哪里转移到哪里”，代码会更容易写对。

第四步：确定初始值和非法状态

常见初始化：

# 求最小值
INF = 10**18
dp = [INF] * (n + 1)
dp[0] = 0

# 求最大值，但某些状态可能无法到达
NEG_INF = -10**18
dp = [NEG_INF] * (n + 1)
dp[0] = 0

# 计数
dp = [0] * (n + 1)
dp[0] = 1       # 空方案有 1 种

# 可行性
dp = [False] * (n + 1)
dp[0] = True    # 什么都不选可以凑出 0

dp[0] 经常是整个转移的起点，不能忽略。

第五步：确定枚举顺序

原则只有一句：

计算当前状态时，它依赖的状态必须已经计算完毕。

例如：

• 普通线性 DP 通常从左到右。
• 区间 DP 通常先枚举较短区间，再枚举较长区间。
• 01 背包的一维写法必须倒序枚举容量。
• 完全背包的一维写法通常正序枚举容量。

---

三、线性 DP

1. 什么是线性 DP

当题目的数据按一条线排列，状态通常按照位置 1, 2, ..., n 依次计算，这类问题常被称为线性 DP。

常见关键词：

• 前 i 个元素
• 以第 i 个元素结尾
• 连续序列
• 把序列分成若干段
• 从左到右处理

线性 DP 不是只有一个固定模板。最常见的两种状态视角是：

1. 前缀型：dp[i] 表示前 i 个元素的答案。
2. 结尾型：dp[i] 表示必须以第 i 个元素结尾的答案。

---

2. 入门例题：爬楼梯

题目

有 n 级台阶，每次走 1 级或 2 级，问走到第 n 级有多少种方法。

状态设计

dp[i] 表示恰好走到第 i 级台阶的方案数。

转移

到达第 i 级的最后一步只有两种可能：

• 从 i-1 走 1 级过来；
• 从 i-2 走 2 级过来。

所以：

$$dp[i] = dp[i-1] + dp[i-2]$$

初始化

dp[0] = 1：站在起点可以看作有一种“什么也不做”的方法。
dp[1] = 1：只能走一次 1 级。

代码

n = int(input())

dp = [0] * (n + 1)
dp[0] = 1

if n >= 1:
    dp[1] = 1

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n])

容易犯的错误

• 忘记处理 n = 0 或 n = 1。
• 不理解 dp[0] = 1。这里的 1 不是说有一级台阶，而是说空方案有一种。

---

3. 结尾型线性 DP：最长上升子序列 LIS

题目

给定序列 a，求最长的严格上升子序列长度。子序列不要求连续，但必须保持原来的先后顺序。

例如：

序列：3 1 2 5 4
一种最长上升子序列：1 2 5
答案：3

为什么不能定义成“前 i 个的答案”直接转移

如果只知道前 i-1 个元素中的最长长度，却不知道这个子序列最后一个数是多少，就不能判断 a[i] 能不能接在它后面。

因此需要把“结尾位置”记录进状态。

状态设计

dp[i] 表示以 a[i] 结尾的最长严格上升子序列长度。

注意：状态要求这个子序列必须选择 a[i]，而且以它结尾。

转移

枚举 i 前面的每一个位置 j：

• 如果 a[j] < a[i]，那么 a[i] 可以接在以 a[j] 结尾的上升子序列后面；
• 新长度为 dp[j] + 1；
• 在所有合法的 j 中取最大值。

$$dp[i] = \max_{0 \le j < i,\ a[j] < a[i]}(dp[j]+1)$$

初始化

每个元素自己都能组成长度为 1 的子序列：

dp = [1] * n

最终答案

最长上升子序列可能在任意位置结束，所以答案是：

max(dp)

而不是一定等于 dp[n-1]。

代码：O(n²) 基础写法

n = int(input())
a = list(map(int, input().split()))

dp = [1] * n

for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

常见错误

• 把严格上升的 < 写成 <=。
• 输出 dp[-1]，但最优子序列不一定以最后一个元素结尾。
• 把“子序列”误认为“连续子数组”。
• 状态说的是“前 i 个的答案”，代码却按“以 i 结尾”转移。

通用结尾型模板

dp = [初始值] * n

for i in range(n):
    for j in range(i):
        if j 能转移到 i:
            dp[i] = min或max(dp[i], dp[j] + 新贡献)

answer = min或max(dp)

---

4. 前缀分段 DP：把序列分成若干合法段

这是一类非常常见的线性 DP。

题目模型

给定长度为 n 的序列，要把整个序列切成若干个连续段。每段必须满足某个条件，求最少段数或最大收益。

状态设计

dp[i] 表示把前 i 个元素全部分完所需的最少段数。

寻找最后一步

假设最后一段是 [j, i]，那么：

• 前 j-1 个元素已经用 dp[j-1] 段分好；
• [j, i] 作为新的一段；
• 如果 [j, i] 合法，总段数就是 dp[j-1] + 1。

因此：

$$dp[i] = \min_{1 \le j \le i,\ [j,i]\ 合法}\{dp[j-1]+1\}$$

初始化

dp[0] = 0：前 0 个元素不需要任何一段。
其他状态先设为无穷大。

通用模板

INF = 10**18
dp = [INF] * (n + 1)
dp[0] = 0

for i in range(1, n + 1):
    for j in range(1, i + 1):
        if 区间_j_i_合法:
            dp[i] = min(dp[i], dp[j - 1] + 1)

print(dp[n])

为什么是 dp[j-1]

最后一段占据 [j, i]，它前面的部分是 [1, j-1]，一共有 j-1 个元素。所以使用 dp[j-1]，不是 dp[j]。

---

5. 完整例题：P1564 膜拜

题意简化

有 n 个同学排成一排，每人崇拜神牛 1 或神牛 2。要将他们分进若干机房，每个机房必须对应原序列中的一个连续区间。

一个机房合法，当且仅当满足下面任意一条：

1. 全部同学都崇拜同一位神牛；
2. 两类同学人数之差不超过 m。

求最少机房数。

状态设计

dp[i] 表示安置前 i 个同学最少需要多少个机房。

转移

枚举最后一个机房从第 j 个同学开始，一直到第 i 个同学：

如果 [j, i] 合法：
dp[i] = min(dp[i], dp[j-1] + 1)

如何快速判断区间是否合法

如果每次都重新遍历 [j, i] 统计两类人数，总复杂度会变成 O(n³)。

可以使用前缀和：

pre1[i] 表示前 i 个同学中崇拜 1 的人数。

于是 [j, i] 中崇拜 1 的人数为：

$$cnt1 = pre1[i] - pre1[j-1]$$

区间长度为 i-j+1，所以崇拜 2 的人数为：

$$cnt2 = (i-j+1)-cnt1$$

合法条件为：

cnt1 == 0 or cnt2 == 0 or abs(cnt1 - cnt2) <= m

前两个条件不能省略。比如 m = 0 时，一个全是 1 的机房人数差很大，但根据题意仍然合法。

完整代码

n, m = map(int, input().split())

a = [0]
for _ in range(n):
    x = int(input())
    a.append(x)

# pre1[i]：前 i 人中崇拜 1 的人数
pre1 = [0] * (n + 1)
for i in range(1, n + 1):
    pre1[i] = pre1[i - 1] + (1 if a[i] == 1 else 0)

INF = 10**9
dp = [INF] * (n + 1)
dp[0] = 0

for i in range(1, n + 1):
    # 枚举最后一个机房的起点 j
    for j in range(1, i + 1):
        cnt1 = pre1[i] - pre1[j - 1]
        length = i - j + 1
        cnt2 = length - cnt1

        legal = (
            cnt1 == 0
            or cnt2 == 0
            or abs(cnt1 - cnt2) <= m
        )

        if legal:
            dp[i] = min(dp[i], dp[j - 1] + 1)

print(dp[n])

复杂度

• 两层循环枚举 i 和 j：O(n²)。
• 前缀和让每个区间的合法性判断降为 O(1)。
• DP 数组和前缀和数组占用 O(n) 空间。

本题常见错误

1. 只按连续相同元素压缩后贪心合并

   合法区间可能从某个相同段的中间开始，也可能在另一个相同段的中间结束。只考虑完整段会漏掉方案。

2. 忘记“全是同一种人”永远合法

   合法性不能只写 abs(cnt1 - cnt2) <= m。

3. 写成三重循环

   区间计数应使用前缀和，不要每次重新扫描区间。

---

6. 线性 DP 总结

常见状态句式

dp[i] 表示前 i 个元素的答案。
dp[i] 表示以第 i 个元素结尾的答案。

核心思考

• 前缀型：最后一步处理了哪一段或哪个元素？
• 结尾型：当前位置可以接在哪些更早的位置后面？

常见坑

• 没说清“前 i 个”还是“以 i 结尾”。
• 下标偏移一位。
• 忘记 dp[0]。
• 最终答案错误地固定在最后一个结尾状态上。
• 区间信息反复计算，没有考虑前缀和。

---

四、背包 DP

1. 什么是背包问题

背包问题的基本模型是：

有若干物品，每个物品有重量（或花费）和价值。在总容量有限的条件下，选择物品，使总价值最大，或求方案数、可行性等。

题目不一定真的出现“背包”两个字。下面这些说法也可能是背包：

• 时间有限，选择任务获得最大收益；
• 预算有限，购买商品获得最大满意度；
• 从若干数字中选择一些，能否凑出目标和；
• 有若干硬币，凑出金额的方法数；
• 每门课程花费时间并得到分数。

识别关键是：

1. 有若干个可选对象；
2. 每个对象消耗某种容量；
3. 选择受到总容量限制；
4. 题目要求最优值、方案数或可行性。

---

2. 01 背包：每个物品最多选一次

标准题目

有 n 个物品，背包容量为 W。第 i 个物品重量为 weight[i]，价值为 value[i]。每个物品最多选一次，求最大总价值。

2.1 二维 DP：最容易理解的写法

状态设计

dp[i][j] 表示只考虑前 i 个物品，背包容量不超过 j 时的最大价值。

最后一步：第 i 个物品选不选

只有两种情况。

不选第 i 个物品

答案与只考虑前 i-1 个物品时相同：

$$dp[i][j] = dp[i-1][j]$$

选择第 i 个物品

前提是 j >= weight[i]。选它之后，剩余容量为 j-weight[i]，价值增加 value[i]：

$$dp[i][j] = dp[i-1][j-weight[i]] + value[i]$$

合并两种选择

$$dp[i][j] = \max\left(dp[i-1][j],\ dp[i-1][j-weight[i]]+value[i]\right)$$

为什么选择物品后仍然看第 i-1 行

因为每个物品最多选一次。选择第 i 个物品后，剩下的方案只能从前 i-1 个物品中产生，不能再次使用第 i 个物品。

初始化

dp[0][j] = 0：没有物品时，最大价值为 0。
dp[i][0] = 0：容量为 0 时，最大价值为 0。

代码

n, W = map(int, input().split())

weight = [0] * (n + 1)
value = [0] * (n + 1)

for i in range(1, n + 1):
    weight[i], value[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(W + 1):
        # 不选第 i 个物品
        dp[i][j] = dp[i - 1][j]

        # 选择第 i 个物品
        if j >= weight[i]:
            dp[i][j] = max(
                dp[i][j],
                dp[i - 1][j - weight[i]] + value[i]
            )

print(dp[n][W])

复杂度

• 时间：O(nW)。
• 空间：O(nW)。

---

2.2 一维空间优化

观察二维转移可知，第 i 行只依赖第 i-1 行，所以可以把第一维压掉：

dp[j] 表示处理完当前已经枚举过的物品后，容量不超过 j 时的最大价值。

代码：

n, W = map(int, input().split())

dp = [0] * (W + 1)

for _ in range(n):
    w, v = map(int, input().split())

    # 01 背包必须倒序枚举容量
    for j in range(W, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[W])

为什么一定要倒序

假设只有一个物品，重量为 2，价值为 3，容量为 4。

如果正序枚举：

j = 2：dp[2] = dp[0] + 3 = 3
j = 4：dp[4] = dp[2] + 3 = 6

但 dp[2] 刚刚已经使用过当前物品，再用它更新 dp[4] 就相当于把同一个物品选了两次，违反“最多选一次”。

倒序枚举时，更新 dp[j] 所读取的 dp[j-w] 仍是处理当前物品之前的旧值，因此不会重复选择当前物品。

记忆口诀：01 背包倒着走，每件物品只一次。

---

3. “恰好装满”与“不超过容量”的区别

这是背包中非常容易忽略的问题。

不超过容量时求最大价值

每种容量都允许什么也不选，因此可以全部初始化为 0：

dp = [0] * (W + 1)

必须恰好装到某个容量

不可达状态不能初始化为 0，否则程序会误以为它们已经可以到达。

NEG_INF = -10**18
dp = [NEG_INF] * (W + 1)
dp[0] = 0

for w, v in items:
    for j in range(W, w - 1, -1):
        if dp[j - w] != NEG_INF:
            dp[j] = max(dp[j], dp[j - w] + v)

最终：

• dp[W] == NEG_INF：无法恰好装满；
• 否则 dp[W] 就是恰好装满时的最大价值。

---

4. 01 背包的另外两种问法

4.1 可行性：能否凑出目标和

dp[j] 表示能否从已经处理的数字中选一些，使总和恰好为 j。

numbers = list(map(int, input().split()))
target = int(input())

dp = [False] * (target + 1)
dp[0] = True

for x in numbers:
    for j in range(target, x - 1, -1):
        dp[j] = dp[j] or dp[j - x]

print(dp[target])

4.2 计数：有多少种选择方案

dp[j] 表示从已经处理的物品中选择一些，总重量恰好为 j 的方案数。

dp = [0] * (W + 1)
dp[0] = 1

for w in weights:
    for j in range(W, w - 1, -1):
        dp[j] += dp[j - w]

print(dp[W])

这两种写法仍然倒序，因为每个对象最多使用一次。

---

5. 完全背包：每种物品可以选无限次

与 01 背包的区别

• 01 背包：每个物品最多选一次。
• 完全背包：每种物品可以选任意多次。

一维代码只差枚举容量的方向：

n, W = map(int, input().split())

dp = [0] * (W + 1)

for _ in range(n):
    w, v = map(int, input().split())

    # 完全背包正序枚举容量
    for j in range(w, W + 1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[W])

为什么正序允许重复选择

更新 dp[j] 时，dp[j-w] 可能已经在本轮加入过当前物品。再加一次当前物品，就自然实现了重复选择。

记忆口诀：完全背包正着走，同种物品可多次。

二维转移的理解

完全背包选择第 i 种物品后，仍然可以继续选择第 i 种，所以选择分支来自当前行：

$$dp[i][j] = \max\left(dp[i-1][j],\ dp[i][j-w_i]+v_i\right)$$

这与 01 背包选择分支来自 dp[i-1][...] 不同。

---

6. 完全背包计数：硬币兑换

题目

有若干种面值的硬币，每种硬币无限个，问凑出 target 有多少种组合。不同顺序不算不同方案。

例如用硬币 [1, 2] 凑 3：

1 + 1 + 1
1 + 2

共 2 种组合，2 + 1 与 1 + 2 是同一种。

代码

coins = list(map(int, input().split()))
target = int(input())

dp = [0] * (target + 1)
dp[0] = 1

for coin in coins:
    for amount in range(coin, target + 1):
        dp[amount] += dp[amount - coin]

print(dp[target])

循环顺序为什么重要

for coin in coins:
    for amount in ...:

这种顺序统计的是组合数，因为硬币种类按固定顺序处理。

如果交换两层循环：

for amount in range(1, target + 1):
    for coin in coins:
        ...

通常统计的是排列数，1+2 和 2+1 会被算成不同方案。

所以遇到计数背包时，不只要判断容量正序还是倒序，还要弄清题目是否区分选择顺序。

---

7. 多重背包：每种物品有数量限制

模型

第 i 种物品重量为 w[i]、价值为 v[i]，最多可以选 count[i] 个。

最容易理解的朴素写法

枚举这一种物品选择几个：

NEG_INF = -10**18
dp = [NEG_INF] * (W + 1)
dp[0] = 0

for w, v, count in items:
    old = dp.copy()
    for capacity in range(W + 1):
        for k in range(count + 1):
            used = k * w
            if used > capacity:
                break
            if old[capacity - used] != NEG_INF:
                dp[capacity] = max(
                    dp[capacity],
                    old[capacity - used] + k * v
                )

这个版本便于理解，但时间可能较慢。

二进制拆分优化

如果某种物品最多有 13 个，可以拆成数量：

1、2、4、6

这些组可以组合出 0 到 13 的任意数量。每组作为一个“最多选一次的新物品”，然后做 01 背包。

dp = [0] * (W + 1)

for w, v, count in items:
    k = 1
    while k <= count:
        group_w = k * w
        group_v = k * v

        for j in range(W, group_w - 1, -1):
            dp[j] = max(dp[j], dp[j - group_w] + group_v)

        count -= k
        k *= 2

    if count > 0:
        group_w = count * w
        group_v = count * v

        for j in range(W, group_w - 1, -1):
            dp[j] = max(dp[j], dp[j - group_w] + group_v)

初学阶段先会朴素写法，再理解二进制拆分即可。

---

8. 分组背包：每组最多选一个

模型

物品被分成若干组，每组中最多选择一个物品。

例如：每门课程有多个学习方案，每门课最多选择一个方案。

转移思路

处理一组时：

• 可以整组都不选；
• 或选择组中的某一个物品；
• 不能选择同组中的两个物品。

dp = [0] * (W + 1)

for group in groups:
    # 每组最多选一个，因此容量倒序
    for j in range(W, -1, -1):
        for w, v in group:
            if j >= w:
                dp[j] = max(dp[j], dp[j - w] + v)

关键是“组”在最外层。处理完一组后再进入下一组。

---

9. 背包 DP 总结表

类型	每个物品能选几次	一维容量顺序	常见提示
01 背包	最多 1 次	倒序	选或不选、每个只能一次
完全背包	无限次	正序	可重复、无限供应
多重背包	最多指定次数	朴素枚举数量或二进制拆分	每种有若干个
分组背包	每组最多选一个	通常倒序，组在最外层	每组选一个方案

10. 背包最常见的错误

1. 01 背包容量写成正序，导致同一物品被重复使用。
2. 完全背包容量写成倒序，导致每种物品只能使用一次。
3. 没分清“容量不超过”与“必须恰好装满”。
4. 求恰好装满时，把所有状态初始化为 0，导致不可达状态被当成可达。
5. 计数问题忘记 dp[0] = 1。
6. 组合数和排列数的循环顺序混淆。
7. 状态含义是“容量恰好为 j”，最后却按“容量不超过 j”解释。
8. 使用二维 DP 时数组过大，没有评估内存。

---

五、区间 DP

1. 什么是区间 DP

区间 DP 用一个区间作为状态：

dp[l][r] 表示区间 [l, r] 的答案。

它常用于下面这些问题：

• 合并相邻元素或区间；
• 从区间左右两端取元素；
• 删除或匹配一段区间；
• 括号匹配；
• 回文相关问题；
• 环形序列合并。

常见关键词：

区间、相邻合并、左右端点、最后一次合并、删除一段、括号、回文

2. 为什么必须按区间长度枚举

大区间的答案通常依赖更小的区间。例如：

dp[l][r] 依赖 dp[l][k] 和 dp[k+1][r]

这两个子区间都比 [l, r] 短。因此需要先计算短区间，再计算长区间。

标准枚举顺序：

for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        # 计算 dp[l][r]

下标推导：

区间长度 = r - l + 1 = length
所以 r = l + length - 1

---

3. 经典例题：石子合并

题目

有 n 堆石子排成一排，第 i 堆有 a[i] 颗石子。

每次只能合并相邻的两堆，合并代价等于这两堆石子的总数。求把所有石子合成一堆的最小总代价。

例如：

石子：1 2 3

方案一：

先合并 1 和 2，代价 3，得到 [3, 3]
再合并 3 和 3，代价 6
总代价 9

方案二：

先合并 2 和 3，代价 5，得到 [1, 5]
再合并 1 和 5，代价 6
总代价 11

最小总代价是 9。

状态设计

dp[l][r] 表示把第 l 堆到第 r 堆合并成一堆的最小代价。

寻找最后一步

不要先想“第一次合并哪两堆”，因为第一次之后的变化很多，不容易描述。

考虑最后一次合并。最后一次之前，区间 [l, r] 一定已经变成了相邻的两大堆：

[l, k] 和 [k+1, r]

其中分界点 k 可以是 l 到 r-1 中的任意位置。

为了完成这种方案，需要：

1. 用 dp[l][k] 的代价把左半段合成一堆；
2. 用 dp[k+1][r] 的代价把右半段合成一堆；
3. 最后合并两堆，代价是整个区间的石子总数。

所以：

$$dp[l][r] = \min_{l \le k < r}\left\{ dp[l][k] + dp[k+1][r] + sum(l,r) \right\}$$

为什么最后合并代价是整个区间的总和

最后合并的两堆分别包含 [l, k] 和 [k+1, r] 的所有石子。两堆之和就是 [l, r] 的石子总数。

使用前缀和计算区间和

定义：

prefix[i] 表示前 i 堆石子的总数。

则：

$$sum(l,r) = prefix[r] - prefix[l-1]$$

这样每次查询区间和只需要 O(1) 时间。

初始化

长度为 1 的区间本身已经是一堆，不需要合并：

$$dp[i][i] = 0$$

其他尚未计算的区间设置为无穷大。

枚举顺序

1. 枚举区间长度 length，从 2 到 n；
2. 枚举左端点 l；
3. 计算右端点 r；
4. 枚举分界点 k。

完整代码

n = int(input())
a = [0] + list(map(int, input().split()))

# 前缀和
prefix = [0] * (n + 1)
for i in range(1, n + 1):
    prefix[i] = prefix[i - 1] + a[i]

INF = 10**18
dp = [[INF] * (n + 1) for _ in range(n + 1)]

# 一个区间只有一堆时，不需要合并
for i in range(1, n + 1):
    dp[i][i] = 0

# 先枚举短区间，再枚举长区间
for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        interval_sum = prefix[r] - prefix[l - 1]

        # 最后一次合并的分界点
        for k in range(l, r):
            dp[l][r] = min(
                dp[l][r],
                dp[l][k] + dp[k + 1][r] + interval_sum
            )

print(dp[1][n])

复杂度

• 状态数约为 O(n²)，因为有许多 [l, r]。
• 每个状态枚举分界点 k，需要 O(n)。
• 总时间复杂度为 O(n³)。
• DP 表占用 O(n²) 空间。

---

4. 手算一次石子合并

以 [1, 2, 3] 为例。

长度为 1

dp[1][1] = 0
dp[2][2] = 0
dp[3][3] = 0

长度为 2

区间 [1, 2] 只有一个分界点 k=1：

dp[1][2] = dp[1][1] + dp[2][2] + (1+2) = 3

区间 [2, 3]：

dp[2][3] = dp[2][2] + dp[3][3] + (2+3) = 5

长度为 3

计算 dp[1][3]：

k = 1：dp[1][1] + dp[2][3] + 6 = 0 + 5 + 6 = 11
k = 2：dp[1][2] + dp[3][3] + 6 = 3 + 0 + 6 = 9

取较小值，所以 dp[1][3] = 9。

这个过程正好说明：DP 会比较所有可能的最后分界点，而不是武断地选择某一个。

---

5. 区间 DP 的两类常见转移

5.1 枚举分界点

适用于合并、拆分问题：

$$dp[l][r] = \min/\max_{l \le k < r} \{dp[l][k] + dp[k+1][r] + cost(l,r,k)\}$$

模板：

for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        dp[l][r] = INF

        for k in range(l, r):
            dp[l][r] = min(
                dp[l][r],
                dp[l][k] + dp[k + 1][r] + cost(l, r, k)
            )

5.2 从左右端点转移

适用于每次从左端或右端取元素的问题：

$$dp[l][r] = \max/min \begin{cases} dp[l+1][r] + 左端贡献\\ dp[l][r-1] + 右端贡献 \end{cases}$$

模板：

for length in range(1, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1

        if l == r:
            dp[l][r] = base_value(l)
        else:
            dp[l][r] = max(
                dp[l + 1][r] + choose_left(l, r),
                dp[l][r - 1] + choose_right(l, r)
            )

---

6. 第二个例子：最长回文子序列

题目

给定字符串 s，求它的最长回文子序列长度。

例如：

s = "bbbab"
最长回文子序列可以是 "bbbb"
答案为 4

状态设计

dp[l][r] 表示字符串区间 s[l:r+1] 中最长回文子序列的长度。

转移

如果两端字符相同：

$$dp[l][r] = dp[l+1][r-1] + 2$$

如果两端不同，那么两端不能同时成为当前回文子序列的一对外层字符。至少舍弃一端：

$$dp[l][r] = \max(dp[l+1][r], dp[l][r-1])$$

初始化

一个字符本身就是长度为 1 的回文：

$$dp[i][i] = 1$$

代码

s = input().strip()
n = len(s)

dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = 1

for length in range(2, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1

        if s[l] == s[r]:
            if length == 2:
                dp[l][r] = 2
            else:
                dp[l][r] = dp[l + 1][r - 1] + 2
        else:
            dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])

print(dp[0][n - 1])

这个例子说明，区间 DP 不一定要枚举分界点，也可能只依赖缩小左右端点后的区间。

---

7. 环形区间问题怎么处理

如果题目把序列首尾相连成一个环，区间没有固定起点。常见处理方法是把数组复制一遍：

b = a + a

然后在长度不超过 n 的区间中计算 DP，最后枚举所有可能起点：

[1, n]、[2, n+1]、...、[n, 2n-1]

这种方法叫“断环成链”。

注意：数组长度变成 2n 后，时间和空间也会增大，必须结合题目数据范围判断是否可行。

---

8. 区间 DP 最常见的错误

1. 直接按左端点从小到大、右端点从小到大枚举，导致依赖的小区间还没算好。
2. r = l + length 少减了 1。
3. 分界点写到 r，产生空区间或越界。正确范围通常是 range(l, r)。
4. 忘记初始化 dp[i][i]。
5. 区间和每次循环重新计算，使复杂度从 O(n³) 变成 O(n⁴)。
6. 求最小值时默认初始化为 0，导致结果始终为 0。
7. 混淆“子串/子数组”和“子序列”。区间 DP 的 [l, r] 表示原数据中的连续区间，但状态内部求的对象有时可以是子序列。
8. 没有从“最后一次操作”思考，导致转移遗漏方案。

---

六、三类 DP 的区别与识别方法

类型	常见状态	核心问题	常见关键词
线性 DP	dp[i]	当前前缀或结尾如何由更早位置得到	前 i 个、以 i 结尾、分段、序列
背包 DP	dp[i][j] 或 dp[j]	当前物品选不选、选几次	容量、重量、价值、预算、凑数
区间 DP	dp[l][r]	区间如何拆成更小区间或缩小端点	相邻合并、左右端点、区间、回文

快速判断流程

看到一道题时，可以按下面顺序提问：

1. 是否有“物品 + 容量限制 + 选择”？
   是 -> 优先考虑背包 DP。

2. 状态是否天然由一个连续区间 [l, r] 描述？
   大区间是否依赖小区间？
   是 -> 优先考虑区间 DP。

3. 是否从左到右处理序列？
   是否关心前 i 个、以 i 结尾或最后一段？
   是 -> 优先考虑线性 DP。

这只是识别线索，不是绝对规则。一道题也可能同时结合多种 DP，例如“树上背包”“区间 DP + 状态压缩”。

---

七、调试 DP 的实用方法

1. 先写状态含义，再写代码

建议在草稿或代码注释中完整写下：

# dp[i] 表示……

如果这句话说不清楚，转移大概率也写不清楚。

2. 检查转移是否覆盖所有“最后一步”

例如分段 DP 中，最后一段的起点可能是任意 j，就应该完整枚举所有 j。不能只根据直觉保留某些位置。

3. 用极小数据手算

推荐测试：

• n = 1；
• 所有元素相同；
• 所有元素不同；
• 容量为 0；
• 某个物品重量刚好等于容量；
• 答案无法到达；
• 最优决策发生在最左端或最右端。

4. 打印 DP 表

学习阶段可以打印中间状态：

print(i, dp)

区间 DP 可以打印二维表：

for row in dp:
    print(row)

观察它是否与手算结果一致。提交 OJ 前记得删除调试输出。

5. 逐项核对下标

重点检查：

前 i 个元素的最后下标是什么？
[j, i] 前面有多少个元素？
区间长度是不是 r-l+1？
range 的右端是否不包含？
输入数组是从 0 还是从 1 开始？

6. 先写正确版本，再做空间优化

背包初学者可以先写二维 DP，确认含义和转移无误后再压缩成一维。不要在状态还没理解时，直接背一维代码。

---

八、学习路线与练习建议

第一阶段：会定义简单一维状态

练习目标：

• 爬楼梯；
• 最大连续子段和；
• 最长上升子序列 O(n²)；
• 最少分段问题。

要求自己每题都写出：状态、转移、初始化、顺序、答案位置。

第二阶段：掌握三种基础背包变化

练习顺序：

1. 二维 01 背包；
2. 一维 01 背包；
3. 完全背包；
4. 恰好装满、可行性、计数；
5. 多重背包与分组背包。

最重要的是理解容量枚举方向，而不是死记模板。

第三阶段：掌握区间枚举顺序

练习顺序：

1. 石子合并；
2. 最长回文子序列；
3. 从两端取数；
4. 环形石子合并。

重点训练从“最后一次操作”寻找分界点。

每做一道题都回答这七个问题

1. dp 状态的准确含义是什么？
2. 当前状态的最后一步是什么？
3. 转移来自哪些更小状态？
4. 初始状态为什么这样设置？
5. 哪些状态不可达，如何表示？
6. 为什么要按这个顺序枚举？
7. 时间和空间复杂度是多少？

如果能不看答案独立说清这七点，就不只是“背会代码”，而是真正理解了这道 DP。

---

九、最终速查表

1. 线性分段 DP

# dp[i]：处理完前 i 个元素的最优答案
INF = 10**18
dp = [INF] * (n + 1)
dp[0] = 0

for i in range(1, n + 1):
    for j in range(1, i + 1):
        if segment_is_valid(j, i):
            dp[i] = min(dp[i], dp[j - 1] + cost(j, i))

2. 结尾型线性 DP

# dp[i]：必须以 i 结尾的最优答案
dp = [base_value] * n

for i in range(n):
    for j in range(i):
        if can_transfer(j, i):
            dp[i] = max(dp[i], dp[j] + contribution(j, i))

3. 01 背包

dp = [0] * (W + 1)

for w, v in items:
    for j in range(W, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)

4. 完全背包

dp = [0] * (W + 1)

for w, v in items:
    for j in range(w, W + 1):
        dp[j] = max(dp[j], dp[j - w] + v)

5. 区间 DP：枚举分界点

INF = 10**18
dp = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    dp[i][i] = 0

for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1

        for k in range(l, r):
            dp[l][r] = min(
                dp[l][r],
                dp[l][k] + dp[k + 1][r] + cost(l, r, k)
            )

6. 三句最重要的记忆

线性 DP：想清楚 dp[i] 是“前 i 个”还是“以 i 结尾”。

背包 DP：先判断每个物品能选几次，再决定容量枚举方向。

区间 DP：从小区间推大区间，优先思考最后一次操作。

---

动态规划真正需要记忆的不是几十个模板，而是同一个思考过程：定义状态，寻找最后一步，列出所有选择，利用已经计算的小状态得到当前状态。 模板只是这个过程写成代码后的结果。