动态规划
题集简介
动态规划，简称DP，它的思想是将一个问题分解为若干个子问题，对每个子问题求最优解，前一个子问题的最优解，为下面的子问题提供了有效信息，依次解决子问题，最后一个子问题就是初始问题的最优解。动态规划应用于子问题重叠的情况，子问题的划分是通过递归实现。为了避免子问题的重复计算，保证每个子问题只求解一次，会将解保存在数组中，是历来竞赛当中的主角，本题集收录了基本的动态规划题、还有背包问题以及动态规划的经典问题等等，供大家练个够！
题目列表
| 题号 | 标题 | 解决/提交 | ||
|---|---|---|---|---|
| 2133 | 信息学奥赛一本通T1269-庆功会 | 简单题 | 120/212 | |
| 2134 | 信息学奥赛一本通T1270-混合背包 | 简单题 | 156/370 | |
| 2135 | 信息学奥赛一本通 T1271-潜水员 | 中等题 | 133/245 | |
| 2136 | 信息学奥赛一本通T1272-分组背包 | 简单题 | 142/272 | |
| 2137 | 信息学奥赛一本通T1273-货币系统 | 中等题 | 131/206 | |
| 2138 | 信息学奥赛一本通T1290-采药 | 简单题 | 213/325 | |
| 2139 | 信息学奥赛一本通T1291-数字组合 | 简单题 | 221/424 | |
| 3056 | 宠物小精灵之收服 | 入门题 | 76/160 | |
| 3057 | 买书 | 入门题 | 110/192 | |
| 3058 | Charm Bracelet | 入门题 | 166/320 | |
| 2140 | 信息学奥赛一本通T1295-装箱问题 | 简单题 | 89/166 | |
| 3059 | 开餐馆 | 入门题 | 67/169 | |
| 3060 | 合并石子 | 入门题 | 75/130 | |
| 1314 | 乘积最大 | 中等题 | 133/203 | |
| 2141 | 信息学奥赛一本通T1276 -编辑距离 | 简单题 | 106/236 | |
| 2142 | 信息学奥赛一本通T1277-方格取数 | 中等题 | 41/335 | |
| 2143 | 信息学奥赛一本通T1278- 复制书稿 | 简单题 | 32/103 | |
| 2144 | 信息学奥赛一本通T1279-橱窗布置 | 难题 | 49/104 | |
| 2145 | 信息学奥赛一本通T1280-滑雪 | 简单题 | 131/254 | |
| 3061 | 公共子序列 | 入门题 | 99/192 |
前往题解：动态规划 题解与参考答案