常用算法之动态规划法

动态规划是一种将原问题拆解为若干子问题的求解方法，常常用于重叠子问题的和最有结构性能的问题。通过动态规划的方法，计算量则圆圆小于一般的解法。原因在于，对于重叠子问题，一般情况下会被重复计算，而动态规划则是将重复的计算简化为计算一次就放入结果表中，在下一次计算时则从结果表中查询，从而直接获得结果，因此使性能得到提升。

动态规划的思想

动态规划与分治法类似，也是将问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。分治法在问题较大且相互不独立的情况下，由于分解得到的子问题数目太多，各个递归子问题被重复计算多次，求解过程呈幂级数增长，其时间复杂度为n的指数时间。与分治法不同，动态规划方法采用自底向上的递推方式求解，并且经分解得到的子问题往往不是相互独立的，根据子问题的相关性，在每步列出可能的局部解中选出能产生最佳解的部分，并将计算过程填表，只要某个子问题被解决,将不会被多次计算，从而减少了算法的时间复杂度。

动态规划建立在最优原则的基础上，在每一步决策上列出各种可能的局部解，按某些条件舍弃肯定不能得到最优解的局部解，通过逐步筛选，减少计算量。依据最优性原理，寻找最优判断序列，不论初始状态如何，下一次决策必须相对前一次决策产生的新状态构成最优序列。每一步都经过筛选，以每一步的最优性来保证全局的最优性。

求解的基本步骤

动态规划是从初始状态计算结果，后续的计算都依赖于前一个计算结果状态，最终获得解的过程。主要过程包括如下：

1. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可 排序 的，否则问题就无法求解。
2. 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
3. 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
4. 寻找终止条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。实际应用中可以按以下几个简化的步骤进行设计：

1. 分析最优解的性质，并刻画其结构特征。
2. 递归的定义最优解。
3. 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
4. 根据计算最优值时得到的信息，构造问题的最优解

适用条件

能采用动态规划求解的问题的一般要具有3个性质：

• 最优子结构性质：最优子结构性质是一种最优化原理，标识如果一个问题的最优解锁包含的所有问题的解也是最优的。
• 子问题重叠性质：子问题重叠标识在把一个大的问题拆解为若干子问题的过程中，在不同的子问题中会重复计算某些问题。动态规划的方法针对子问题重叠计算的问题，将每个子问题求解的结果存入子问题结果表中，当再次计算子问题时，首先从结果表中查询是否已经计算过，如果已经计算过则直接获取结果，如果没有则直接进行计算，并将计算的结果存入结果表中。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
• 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

动态规划实例：斐波那契数列计算

800年前，意大利的数学家斐波纳契出版了惊世之作《算盘书》。在《算盘书》里，他提出了著名的“兔子问题”：假定一对兔子每个月可以生一对兔子，而这对新兔子在出生后第二个月就开始生另外一对兔子，这些兔子不会死去，那么一对兔子一年内能繁殖多少对兔子？答案是一组非常特殊的数字：1，1，2，3，5，8，13，21，34，55，89……不难发现，从第三个数起，每个数都是前两数之和，这个数列则称为“斐波纳契数列”，其中每个数字都是“斐波纳契数”。

斐波纳契数列还暗含着许多有趣的数字规律，如从第3个数开始每隔两个必是2的倍数，从第4个数开始每隔3个必是3的倍数，从第5个数开始每隔4个必是5的倍数……另外，这个数列最具有和谐之美的地方是，越往后，相邻两项的比值会无限趋向于黄金比0.61803……即[5^(1/2)-1]/2。但这个伟大的发现在当时一直不受数学们的青睐与认可，直到19世纪，斐波纳契数列才在该领域占有一席之地并引发出了许多重要的应用。像斐波纳契方块，斐波纳契螺旋以及斐波纳契数，在生活中都可以见到类似的图案，譬如说海螺和蜗牛壳等等。

裴波那契数列的递归实现：

def fib(n):
    if n==0 or n==1:
        return n
    else:
        return fib(n-1)+fib(n-2)

这种递归的时间复杂度是O(2^n)水平，我们将递归树画出如下：

可以看出进行了重复的计算，为了避免重复的计算操作，可以将分解的子问题的解，用一个字典存起来。每次判断如果字典中已经有了计算过得值，则不再进行计算，直接取值就可以了。这样便大大减少了算法的计算量。

裴波那契数列的动态规划实现：

d = {}
 
def fib(n):
    if n == 0 or n == 1:
        d[n] = n
        return n
 
    if n not in d:
        d[n] = fib(n - 1) + fib(n - 2)
    return d[n]

使用记忆化搜索，记录斐波那契的值，此时时间复杂度已经是O(n)级别。 在使用递归的过程中实际是自上而下的解决问题，而如果我们自下而上的解决问题，即将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案，这就是动态规划。

与动态规划相关的问题还有很多，包括背包问题、最长公共子序列、Floyd-Warshall算法、Viterbi算法等。由于涉及到的内容较多，后续的文章中再做分享。