本文出自 http://blog.csdn.net/shuangde800
刘汝佳《算法竞赛入门经典-训练指南》的动态规划部分的习题Beginner 打开
这个专题一共有25题，刷完后对dp的感觉提升了不少。
现把解题报告整理了一下，希望对大家能有帮助。
入门习题 （Exercises: Beginner）
| UVa11584 | Partitioning by Palindromes | 入门题目 |
| LA4256 | Salesman | 入门题目 |
| UVa10534 | Wavio Sequence | 可以转化为经典问题，时间O(nlogn) |
| UVa11552 | Fewest Flops | 序列划分模型；状态设计 |
| UVa11404 | Palindromic Subsequence | 可以转化为LCS |
| LA4731 | Cellular Network | 需要一点概率知识和推理 |
| UVa11795 | Mega Man's Missions | 基础的集合动态规划 |
| LA4727 | Jump | Joseph问题的变形 |
| LA3530 | Martian Mining | 模型简单，但需要减少重复计算 |
| UVa10564 | Paths through the Hourglass | 类似01 背包问题 |
| UVa10817 | Headmaster's Headache | 集合动态规划 |
| LA2038 | Strategic Game | 树上动态规划（基础题） |
| LA3363 | String Compression | 字符串动态规划 |
| LA2031 | Dance Dance Revolution | 以跳舞机为背景的题目 |
| LA4643 | Twenty Questions | 有趣的问题；比较基础的动态规划 |
| (extra)UVa10163 | Storage Keepers | |
| (extra)UVa10453 | Make Palindrome | |
| *(extra)UVa10254 | The Priest Mathematician | |
| **(extra)UVa437 | The Tower of Babylon | |
| **(extra)UVa442 | Matrix Chain Multiplication | 最优矩阵乘法 |
| **(extra)UVa473 | Raucous Rockers | 可以优化 |
| **(extra)UVa590 | Always on the Run | |
| **(extra)UVa607 | Scheduling Lectures | |
| **(extra)UVa662 | Fast Food | 可以优化 |
| **(extra)UVa672 | Gangsters |
11584 - Partitioning by Palindromes 题解
11404 - Palindromic Subsequence 题解
10564 - Paths through the Hourglass 题解
10817 - Headmaster's Headache 题解
1291 - Dance Dance Revolution 题解
10254 - The Priest Mathematician 题解
442 - Matrix Chain Multiplication 题解