动态规划,简称DP,它的思想是将一个问题分解为若干个子问题,对每个子问题求最优解,前一个子问题的最优解,为下面的子问题提供了有效信息,依次解决子问题,最后一个子问题就是初始问题的最优解。动态规划应用于子问题重叠的情况,子问题的划分是通过递归实现。为了避免子问题的重复计算,保证每个子问题只求解一次,会将解保存在数组中,是历来竞赛当中的主角,本题集收录了基本的动态规划题、还有背包问题以及动态规划的经典问题等等,供大家练个够!
题号 | 标题 | 解决/提交 | ||
---|---|---|---|---|
2133 | 信息学奥赛一本通T1269-庆功会 | 简单题 | 86/158 | |
2134 | 信息学奥赛一本通T1270-混合背包 | 简单题 | 117/271 | |
2135 | 信息学奥赛一本通 T1271-潜水员 | 中等题 | 93/166 | |
2136 | 信息学奥赛一本通T1272-分组背包 | 简单题 | 96/203 | |
2137 | 信息学奥赛一本通T1273-货币系统 | 中等题 | 99/153 | |
2138 | 信息学奥赛一本通T1290-采药 | 简单题 | 175/275 | |
2139 | 信息学奥赛一本通T1291-数字组合 | 简单题 | 170/307 | |
3056 | 宠物小精灵之收服 | 入门题 | 38/78 | |
3057 | 买书 | 入门题 | 61/113 | |
3058 | Charm Bracelet | 入门题 | 26/92 | |
2140 | 信息学奥赛一本通T1295-装箱问题 | 简单题 | 66/128 | |
3059 | 开餐馆 | 入门题 | 35/106 | |
3060 | 合并石子 | 入门题 | 52/104 | |
1314 | 乘积最大 | 中等题 | 65/96 | |
2141 | 信息学奥赛一本通T1276 -编辑距离 | 简单题 | 78/182 | |
2142 | 信息学奥赛一本通T1277-方格取数 | 中等题 | 25/283 | |
2143 | 信息学奥赛一本通T1278- 复制书稿 | 简单题 | 22/56 | |
2144 | 信息学奥赛一本通T1279-橱窗布置 | 难题 | 20/57 | |
2145 | 信息学奥赛一本通T1280-滑雪 | 简单题 | 91/186 | |
3061 | 公共子序列 | 入门题 | 71/145 |