第8次内容

##上周回顾-动态规划之区间DP

线性DP的扩展，就是将状态定义为区间，而不是单个元素。例如，给定一个数组，求区间和，或者区间最大值，等等。

1. 区间DP的定义

区间DP（Interval DP）是一种动态规划问题，其状态定义为某个区间内的最优解。例如，对于一个数组arr[1...n]，我们定义一个二维的DP表dp[i][j]表示从第i个元素到第j个元素的某个最优解。 状态转移方程：dp[i][j] = min(dp[i][j-1], dp[i+1][j], dp[i+2][j-1], ..., dp[i+k-1][j-k+1])，其中k是区间长度。

2. 区间DP的解题步骤

（1） 确定状态定义：区间DP的状态定义为某个区间内最优解。 （2） 寻找状态转移方程：根据问题的具体要求，确定如何从子区间转移到当前区间的最优解。 （3） 设置边界条件：例如，对于空区间或单个元素的情况。 （4） 按顺序迭代求解：从小到大推进，避免重复计算。 （5） 输出结果：根据题意输出最终答案。 （6） 思考：区间DP的解题步骤与线性DP的解题步骤相似，但状态定义和转移方程不同。

3. 区间DP的典型问题

（1）矩阵连乘问题

本周内容之区间DP例题讲解

1. 石子合并问题

石子合并问题

本周内容之01背包问题

01背包问题

这是一个经典的 0-1 背包问题，要求使用 二维动态规划数组 求解。

---

🧠 问题分析

• 状态定义：
  设 dp[i][j] 表示从前 i 个物品中选择，且背包容量为 j 时，能获得的最大价值。

• 状态转移方程：
  对于第 i 个物品（体积 v[i-1]，价值 w[i-1]，因为物品从 0 开始索引）：

  • 如果不选第 i 个物品：dp[i][j] = dp[i-1][j]
  • 如果选第 i 个物品（前提是 j >= v[i-1]）：dp[i][j] = dp[i-1][j - v[i-1]] + w[i-1]
  • 所以：

    dp[i][j] = dp[i-1][j]
    if j >= v[i-1]:
        dp[i][j] = max(dp[i][j], dp[i-1][j - v[i-1]] + w[i-1])
    

• 初始条件：
  dp[0][j] = 0 对所有 j（没有物品可选，价值为 0）

• 答案：
  dp[N][V]

---

✅ 求解步骤（举例说明）

假设输入：

3 4
1 15
2 20
3 30

• N=3, V=4
• 物品：(1,15), (2,20), (3,30)

构建 dp[4][5] 表格（i 从 0 到 3，j 从 0 到 4）：

i\j	0	1	2	3	4
0	0	0	0	0	0
1	0	15	15	15	15
2	0	15	20	35	35
3	0	15	20	35	45

最终答案：dp[3][4] = 45

---