动态规划的核心是状态、阶段和状态转移方程(决策)。

登录以参加训练计划

动态规划

动态规划是一种用途很广的问题求解方法,它本身并不是一个特定的算法,而是一种手段、思想。

动态规划其实是运筹学的一种最优化方法,是求解决策过程(decision process)最优化的数学方法。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

章节 1. 最初的最初

开放

题目 尝试 AC 难度
211   菲波那契数 30 13 5
212   爬楼梯 5 0 10
213   上台阶 2 1 10

章节 2. DP初步

开放

题目 尝试 AC 难度
201   最长上升子序列 22 4 9
202   最长公共子序列 11 2 10
241   最少硬币问题 8 4 10
198   求最长不下降序列 7 3 10
USACO1017   1.5.1 [IOI1994]数字三角形 Number Triangles 20 5 8
242   最大子段和 7 4 10
252   编辑距离 9 2 10
253   摆花 0 0 (无)
254   大师 0 0 (无)
259   最大上升子序列和 0 0 (无)
260   三角形最佳路径问题 0 0 (无)
200   合唱队形 15 3 9
199   拦截导弹(Noip1999) 9 3 10
CSPJ2020D   方格取数 (Grid Numbers Picking) 3 3 10

章节 3. 背包DP

开放

题目 尝试 AC 难度
257   01背包问题 9 2 10
258   完全背包问题 2 1 10
T1267   【例9.11】01背包问题 1 1 10
D1051   01背包输出方案 7 2 10
T1268   【例9.12】完全背包问题 2 2 10
T1269   【例9.13】庆功会(多重背包) 2 1 10
T1270   【例9.14】混合背包 1 1 10
T1271   【例9.15】潜水员(二维背包) 2 1 10
T1272   【例9.16】分组背包 1 1 10
T1273   【例9.17】货币系统(装箱方案数) 3 1 10
T1295   装箱问题(装箱剩余空间) 4 2 10
TRN205   背包问题 - 扩展题单 0 0 (无)
1335   分配礼物 6 3 10

章节 4. 线性DP

开放

题目 尝试 AC 难度
201   最长上升子序列 22 4 9
198   求最长不下降序列 7 3 10
199   拦截导弹(Noip1999) 9 3 10
200   合唱队形 15 3 9
240   数字金字塔 6 3 10

章节 5. 区间DP

开放

题目 尝试 AC 难度
201   最长上升子序列 22 4 9
198   求最长不下降序列 7 3 10
199   拦截导弹(Noip1999) 9 3 10
200   合唱队形 15 3 9
240   数字金字塔 6 3 10
T1274   石子合并 7 3 10
274   石子合并之圆形操场 11 3 9
275   能量项链「区间 dp + 头尾处理 + 环处理」 2 2 10
276   括号配对 13 2 9
1381   回文之最小编辑 2 2 10
1380   正则括号括号匹配 5 2 10
1403   [USACO16OPEN]248 G 4 1 10
 
参加人数
5
创建人