动态规划,简称DP,它的思想是将一个问题分解为若干个子问题,对每个子问题求最优解,前一个子问题的最优解,为下面的子问题提供了有效信息,依次解决子问题,最后一个子问题就是初始问题的最优解。动态规划应用于子问题重叠的情况,子问题的划分是通过递归实现。为了避免子问题的重复计算,保证每个子问题只求解一次,会将解保存在数组中,是历来竞赛当中的主角,本题集收录了基本的动态规划题、还有背包问题以及动态规划的经典问题等等,供大家练个够!
题号 | 标题 | 解决/提交 | ||
---|---|---|---|---|
2127 | 信息学奥赛一本通T1258- 数字金字塔 | 中等题 | 291/505 | |
2124 | 信息学奥赛一本通T1259-求最长不下降序列 | 中等题 | 344/1156 | |
2123 | 信息学奥赛一本通T1260-拦截导弹 | 简单题 | 238/667 | |
3049 | 城市交通路网 | 入门题 | 70/292 | |
2125 | 信息学奥赛一本通TT1262-挖地雷 | 简单题 | 85/179 | |
2126 | 信息学奥赛一本通T1263-友好城市 | 中等题 | 126/266 | |
2128 | 信息学奥赛一本通T1264-合唱队形 | 中等题 | 63/113 | |
1265 | 青年歌手大奖赛_评委会打分 | 中等题 | 550/949 | |
2130 | 信息学奥赛一本通T1266 -机器分配 | 中等题 | 59/88 | |
3050 | 最长上升子序列 | 入门题 | 533/1165 | |
3041 | 最大子矩阵 | 入门题 | 100/198 | |
3051 | 登山 | 入门题 | 121/361 | |
2983 | 花生采摘 | 入门题 | 5/97 | |
3052 | 最大上升子序列和 | 入门题 | 159/331 | |
3053 | 怪盗基德的滑翔翼 | 入门题 | 112/236 | |
3054 | 最低通行费 | 入门题 | 154/284 | |
3055 | 三角形最佳路径问题 | 入门题 | 61/86 | |
2123 | 信息学奥赛一本通T1260-拦截导弹 | 简单题 | 238/667 | |
2131 | 信息学奥赛一本通T1267-01背包问题 | 简单题 | 820/1873 | |
2132 | 信息学奥赛一本通T1268-完全背包问题 | 简单题 | 719/1715 |