(算法理论) 动态规划和（Python）

动态规划

基本思想

为了解决一个给定的问题, 我们必须将该问题是通过解决若干个相关联的小而简单的subproblem是不可能完成的任务, 然后将这些小问題的解决方案结合起来就可以得到原来那个复杂问題的答案. 通常情况下, 存在大量的重叠性, 因此设计动态规划算法时就自然地采用了分治策略, 这样不仅减少了计算量, 而且一旦某个特定subproblem已经被解决, 则将其结果记录下来以便后续快速访问. 这种方法特别适用于那些随着输入规模增大而重复求解次数呈指数级增长的问题.

明确三个事情：

1. 目标问题
2. 状态的定义：opt[n]
3. 状态转移方程：opt[n]=best_of(opt[n-1]，opt[n-2])

分治与动态规划

共同点：它们都强调原问题必须具备最优子结构特性，并采用分阶段处理的方式将大问题分解为若干个规模较小且容易解决的部分（即规模较小的子问题）。接着通过整合这些小部分的解决方案来构建整个问题的整体解决方案。

其分治法将其分解后的子问题是相互独立的，并采用递归方式加以解决；而动态规划则将其分解后的子问题视为具有相互关联且存在重叠的部分，并需进行存储，在这种情形下多采用迭代的方式求解。

步骤

1. 解决一个问题的最佳方案
2. 将大问题是拆分为若干个较小的问题
3. 子问题是更小的问题，并且它