动态规划
题集简介
动态规划，简称DP，它的思想是将一个问题分解为若干个子问题，对每个子问题求最优解，前一个子问题的最优解，为下面的子问题提供了有效信息，依次解决子问题，最后一个子问题就是初始问题的最优解。动态规划应用于子问题重叠的情况，子问题的划分是通过递归实现。为了避免子问题的重复计算，保证每个子问题只求解一次，会将解保存在数组中，是历来竞赛当中的主角，本题集收录了基本的动态规划题、还有背包问题以及动态规划的经典问题等等，供大家练个够！
题目列表
| 题号 | 标题 | 解决/提交 | ||
|---|---|---|---|---|
| 2127 | 信息学奥赛一本通T1258- 数字金字塔 | 中等题 | 339/582 | |
| 2124 | 信息学奥赛一本通T1259-求最长不下降序列 | 中等题 | 369/1385 | |
| 2123 | 信息学奥赛一本通T1260-拦截导弹 | 简单题 | 299/806 | |
| 3049 | 城市交通路网 | 入门题 | 84/324 | |
| 2125 | 信息学奥赛一本通TT1262-挖地雷 | 简单题 | 114/231 | |
| 2126 | 信息学奥赛一本通T1263-友好城市 | 中等题 | 158/318 | |
| 2128 | 信息学奥赛一本通T1264-合唱队形 | 中等题 | 76/130 | |
| 1265 | 青年歌手大奖赛_评委会打分 | 中等题 | 627/1088 | |
| 2130 | 信息学奥赛一本通T1266 -机器分配 | 中等题 | 88/148 | |
| 3050 | 最长上升子序列 | 入门题 | 1089/2240 | |
| 3041 | 最大子矩阵 | 入门题 | 146/280 | |
| 3051 | 登山 | 入门题 | 169/492 | |
| 2983 | 花生采摘 | 入门题 | 8/118 | |
| 3052 | 最大上升子序列和 | 入门题 | 194/384 | |
| 3053 | 怪盗基德的滑翔翼 | 入门题 | 158/338 | |
| 3054 | 最低通行费 | 入门题 | 323/513 | |
| 3055 | 三角形最佳路径问题 | 入门题 | 212/271 | |
| 2123 | 信息学奥赛一本通T1260-拦截导弹 | 简单题 | 299/806 | |
| 2131 | 信息学奥赛一本通T1267-01背包问题 | 简单题 | 1051/2323 | |
| 2132 | 信息学奥赛一本通T1268-完全背包问题 | 简单题 | 872/2063 |
前往题解：动态规划 题解与参考答案