第九章 动态规划
登录以参加训练计划
本章课件
训练说明
本章共 50 道题，按课件知识点分成 5 组：基础与 DAG 上的 DP、线性 DP、背包 DP、区间与划分 DP、二维表与记忆化。 先看课件对应小节，再按组完成练习。
章节 1. 基础与 DAG 上的 DP
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P5269 数字金字塔 | 48 | 11 | 7 |
| P5271 拦截导弹 | 22 | 5 | 8 |
| P5272 城市交通路网 | 21 | 3 | 9 |
| P5273 挖地雷 | 12 | 4 | 9 |
| P5274 友好城市 | 22 | 7 | 7 |
| P5277 机器分配 | 8 | 2 | 10 |
章节 2. 线性 DP
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P5270 求最长不下降序列 | 33 | 4 | 9 |
| P5275 合唱队形 | 25 | 6 | 8 |
| P5276 最长公共子序列 | 29 | 8 | 7 |
| P5303 编辑距离 | 13 | 4 | 9 |
| P5278 最长上升子序列 | 19 | 7 | 7 |
| P5279 最大子矩阵 | 6 | 3 | 10 |
| P5280 登山 | 23 | 6 | 8 |
| P5282 最大上升子序列和 | 16 | 7 | 8 |
| P5283 怪盗基德的滑翔翼 | 13 | 7 | 8 |
| P5286 拦截导弹 | 9 | 5 | 9 |
| P5308 公共子序列 | 7 | 5 | 9 |
| P5309 计算字符串距离 | 9 | 4 | 9 |
| P5312 大盗阿福 | 13 | 5 | 9 |
| P5313 股票买卖 | 5 | 3 | 10 |
| P5316 Maximum sum | 4 | 1 | 10 |
| P5317 最长公共子上升序列 | 5 | 1 | 10 |
章节 3. 背包 DP
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P5287 01背包问题 | 14 | 7 | 8 |
| P5288 完全背包问题 | 22 | 8 | 7 |
| P5289 庆功会 | 13 | 6 | 8 |
| P5290 混合背包 | 12 | 5 | 9 |
| P5291 潜水员 | 8 | 5 | 10 |
| P5292 分组背包 | 10 | 6 | 9 |
| P5293 货币系统 | 13 | 3 | 9 |
| P5294 采药 | 12 | 6 | 9 |
| P5295 数字组合 | 15 | 4 | 9 |
| P5296 宠物小精灵之收服 | 8 | 1 | 10 |
| P5297 买书 | 12 | 2 | 10 |
| P5298 Charm Bracelet | 13 | 6 | 8 |
| P5299 装箱问题 | 9 | 6 | 9 |
| P5310 糖果 | 12 | 3 | 9 |
| P5314 鸣人的影分身 | 4 | 2 | 10 |
| P5315 数的划分 | 5 | 3 | 10 |
章节 4. 区间与划分 DP
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P5301 合并石子 | 16 | 7 | 8 |
| P5302 乘积最大 | 6 | 2 | 10 |
| P5305 复制书稿 | 8 | 1 | 10 |
| P5306 橱窗布置 | 6 | 3 | 10 |
| P5311 鸡蛋的硬度 | 4 | 2 | 10 |
章节 5. 二维表与记忆化
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P5304 方格取数 | 8 | 3 | 10 |
| P5307 滑雪 | 8 | 3 | 10 |
| P5281 摘花生 | 13 | 4 | 9 |
| P5284 最低通行费 | 9 | 6 | 9 |
| P5285 三角形最佳路径问题 | 11 | 8 | 8 |
| P5300 开餐馆 | 8 | 4 | 10 |
| P4982 高效工作 | 3 | 1 | 10 |