动态规划

动态规划入门

习题

• 洛谷 P1002. 过河卒（参考数字金字塔）
• 洛谷 P1281. 书的复制（参考机器分配）
• YBT 1303. 鸣人的影分身（记忆化搜索）
• YBT 1304. 数的划分（记忆化搜索）

背包问题

• YBT 1271. 潜水员（二维费用背包）
• YBT 1273. 货币系统（完全背包）
• YBT 1293. 买书（完全背包）
• YBT 1296. 开餐馆（线性 DP）

习题

• 洛谷 P1049. 装箱问题（01 背包）
• YBT P1294. charm bracelet
• YBT P1299. 糖果
• 洛谷 P1060. 开心的金明（01 背包）
• 洛谷 P1025. 数的划分（01 背包）
• 洛谷 P2347. 砝码称重（多重背包）
• 洛谷 P1336. 最佳课题选择（分组背包）
• 洛谷 P1782. 旅行商的背包（混合背包）
• 洛谷 P1941. 飞扬的小鸟（完全背包）

线性动态规划

习题

• YBT 1283. 登山（LIS）
• YBT 1286. 怪盗基德的滑翔翼（LIS）
• YBT 1259. 求最长不下降序列（LIS）
• YBT 1285. 最大上升子序列和
• YBT 1265. 最长公共子序列（LCS）
• AcWing 899. 编辑距离
• AcWing 312. 乌龟棋
• 洛谷 P1594. 护卫队
• 洛谷 P1854. 花店橱窗布置

区间动态规划

习题

• YBT 1301. 大盗阿福
• YBT 1302. 股票买卖
• YBT 1300. 鸡蛋的硬度
• YBT 1197. 山区建小学