DP基础、背包问题、子序列子串问题、其他DP问题
Login to join training plan
动态规划中的Programming指的是一种“表格法”，它合理安排子问题求解顺序，使得每个子问题只求解一次，将解保存在一个表格中，需要的时候查表即可。 DP的第一种动机是利用递归的重叠子问题，进行记忆化求解，即先用递归法解决问题，再利用重叠子问题转为DP。 DP的第二种动机是把问题看作多阶段决策过程。 DP常常用于求解多阶段决策最优化问题。
Section 1. DP基础
In Progress
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| T1258 【例9.2】数字金字塔 | 68 | 38 | 3 |
| T1290 采药 | 376 | 53 | 8 |
| T1266 【例9.10】机器分配 | 143 | 37 | 7 |
| T1284 摘花生 | 87 | 33 | 5 |
| T1287 最低通行费 | 19 | 11 | 6 |
| T1288 三角形最佳路径问题 | 19 | 17 | 4 |
Section 2. 背包类问题
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| T1267 【例9.11】01背包问题 | 29 | 22 | 2 |
| T1268 【例9.12】完全背包问题 | 59 | 21 | 5 |
| T1269 【例9.13】庆功会 | 130 | 40 | 6 |
| T1271 【例9.15】潜水员 | 58 | 20 | 6 |
| T1272 【例9.16】分组背包 | 90 | 23 | 7 |
| T1273 【例9.17】货币系统 | 93 | 16 | 8 |
| T1270 【例9.14】混合背包 | 58 | 23 | 5 |
| T1293 买书 | 46 | 19 | 5 |
| T1291 数字组合 | 57 | 15 | 7 |
| T1292 宠物小精灵之收服 | 13 | 6 | 8 |
| T1296 开餐馆 | 44 | 11 | 7 |
Section 3. 子序列子串类问题
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| T1281 最长上升子序列 | 115 | 43 | 5 |
| T1260 【例9.4】拦截导弹(Noip1999) | 47 | 19 | 5 |
| T1263 【例9.7】友好城市 | 167 | 33 | 7 |
| T1285 最大上升子序列和 | 96 | 23 | 7 |
| T1265 【例9.9】最长公共子序列 | 140 | 38 | 6 |
| P516 合唱队形 | 64 | 16 | 7 |
| T1306 最长公共子上升序列 | 8 | 1 | 10 |
- Enrollees
- 30
- Created By
-
CH (chenhui)
