动态规划（Dynamic Programming）基础
动态规划问题在比赛中的考点丰富，因为其代码难度一般不大，更多的是思考和发现模型的能力。所以有关于动态规划的部分将会区便于其他部分，会有更少的代码，而去展示更多的思考过程和理论知识。
动态规划和分治的区别
动态规划（Dynamic Programming）与分治方法相似，都是通过组合子问题的解来求解原问题。分治方法将问题划分为互不相交的子问题，递归的求解子问题，再讲他们组合起来，求出原问题的解。与之相反的，动态规划适用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做许多不必要的工作，它会反复的求解这种公共子子问题。而动态规划算法中对每个子子问题都只求解一次，将其解保存在一个表格中，从而不用每次求解一个子子问题的时候都要重新计算，避免这种不必要的计算工作。（摘自《算法导论》第三版 第15章）
一般我们都用动态规划来求解最优化问题。他们的共同特征是，有很多个可行解，我们要在这些可行解中找到一个最大的（或者最小的）解。我们可能并不关心这个解是什么，有几个，只要这个解的评价函数对我们来说是我们想要的最大（或者最小）的可以了。
动态规划中的重要性质
- 具有最优子结构
- 状态无后效性
- 有重叠子问题
最优子结构
最优子结构想表达的是，如果一个问题的最优解包含其子问题的最优解，那么我们就称这个问题有最优子结构性质。
也就是说，一个问题的最优解一定是由其各个子问题的最优解组合而成的。
关于是否满足最优子结构的判断
- 证明问题最优解的第一个组成部分是一个选择。因为这样的选择会产生多个待解的资额问题。
- 假定已经产生了一个最优的选择。
- 判断根据这个最优的选择会产生哪些子问题。这些子问题应该如何表示。
- 利用反证法。证明子问题如果不是最优解，那么可以将这个解从原问题中去掉，换上相对的最优解。从而产生了一个比假定更优的解，和假定是最优解矛盾。
重叠子问题
这个问题相对就容易理解很多。如果我们在递归求解的过程中，反复的求解了相同的子问题，那么就称这个问题有重叠子问题。
这也是动态规划在时间上相较于分治算法的关键。因为我们可以把这些重叠的子问题放在一个备忘录里记下来，避免重复不必要的计算。
状态的无后效性
状态的无后效性指的是，当一个状态被确定之后，一定不会被在其之后确定的状态所影响。也就是说，每个状态的确定都不会影响到之前已经确定的状态。 或者说，一个子问题的解是在子子问题中选择得到的，那么在计算出子问题的解之后，子问题的解不会影响到子子问题。
只有一个问题满足了这三个条件之后，我们才能考虑用动态规划算法去解决它。
设计动态规划算法的一般步骤
设计一个动态规划算法整体上分为两个步骤：
- 设计状态表达式
- 设计状态转移方程
状态表达式 就是对我们所说的问题的一般描述。状态表达式的选择又取决于我们如何给这个问题划分求解的阶段，也就是为这个问题的每一个阶段，设计一个独一无二的表达式来表示他们，并且这个状态表达式的选择应该是满足无后效性的。
状态转移方程 就是我们对一个问题如何由其子问题组成所做出的决策的一般描述。状态转移方程应该描述：
- 一个状态的解可以在哪些状态中选择
- 以何种条件在这些状态中选择出一个或多个，作为组成解状态的子状态
- 被选择出的一个或多个状态以何种方式组合起来，形成了当前状态的解
当这两个问题被解决了之后，一个动态规划算法的框架已经基本成型了。剩下的工作就是：
- 确定边界条件
- 计算时间和空间复杂度
- 判断是否满足题目要求，如果不满足应该如何优化，或者放弃这个思路
例子
说了这么多的理论知识，需要一个例题来看一下都是怎么被运用进去的。
有
n个重量和价值分别问和的物品。从这些物品中选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
数据范围：
现在显然，我们的问题是，有n个物品，放进W的背包里。我们可以把这个问题记作：(n, W)。这个也就是我们要最终求解问题。这个问题，可能的子问题有多少种呢？如果我们把最后一个物品的重量和价值分别记作lw和lv的话。如果我们考虑选了这个物品进入最后的背包，那么子问题的范围应该是：(0, n-lv)到(n-1, n-lv)。如果我们考虑不放入背包的话，(0, n)到(n-1, n)。只不过这些问题在被推导出最终解的时候的方式是不一样的。
那么这些问题显然是满足我们上面说的三个条件的，有最优子结构、没有后效性和有重叠子问题。（这部分可以自己去考虑一下）。
我们可以根据上面的这个表示方法，设计出我们的状态表达式。我们用dp[i][j]去表示，当前考虑到第i个物品，放入一个大小是j的背包里所得到的最大的价值。这个状态的定义和我们上面对子问题的划分方式是一样的。
- 那么这个状态的的解可以在哪些解中选择呢？考虑我们的状态的表示，显然应该是
dp[i-1][k]。如果选择要了第i的物品的话，k的取值范围应该是；如果选择不要第i个物品的话，k的取值范围应该是。 - 条件当然是在这些状态里面选择一个使最后价值最大的了。如果选择了第
i个物品的话，结果应该是子问题的价值加上第i个物品的价值；不选的话，就应该是子问题的价值。 - 挑选出了一个之后，按照上面说的方法选择是否和第
i个物品的价值求和。
所以我们就得到了我们的状态转移方程：
边界条件也很容易确定，当一件东西都没有的时候，也就是dp[0][0]的时候，价值显然是0。其他的时候都还没被计算到，可以赋值称无穷大，也可以判断一下是否被计算到。
时间复杂度方面，每个状态都被算了一次，每次计算枚举了j种状态，所以时间复杂度是；空间复杂度是。是满足题意的。