动态规划
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| dynamic programming | 动态规划 | dòng tài guī huà |
| dependency order | 依赖顺序 | yī lài shùn xù |
| DP table | DP 表 | DP biǎo |
记住，别重算
- 动态规划 dynamic programming 对重叠子问题只解一次、存起来、由已存答案搭更大的解。设计三件套：递推式、基础情形、填 DP 表 DP 表 的依赖顺序 dependency order。
{exercise:uni-cs1004-dp}
练习
DP 设计是指——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
三件套：格子的含义、从哪起、朝哪填。
那个并非指数的指数
- 朴素斐波那契反复重算：$F(30)$ 调用 2,692,537 次——调用次数服从同一递推、指数级。记忆化后：29 个子问题，$\Theta(n)$。
- 硬币表（1、3、4）：$dp[i] = 1 + \min(dp[i - c])$——$dp[6] = 2$（3+3），贪心付 3。
{exercise:uni-cs1004-fib}
练习
朴素 fib(30) 调用——次。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
调用次数本身按斐波那契指数增长；记忆化后 29 个子问题。
背包，小而精确
- 容量 7、物品 (1,1)、(3,4)、(4,5)、(5,7)：按容量填表得 $dp[7] = 9$（物品 2 与 3：重 7 值 9）。
- 每个格子都是一个有理由的决策——表即解释。沿箭头方向迭代，绝不读未写的格子。
{exercise:uni-cs1004-knapsack}
练习
容量 7、物品 (1,1)(3,4)(4,5)(5,7)：dp[7] = ——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
物品 2 与 3：重 7 值 9。