动态规划是一种将原问题拆解为若干子问题的求解方法，常常用于重叠子问题的和最有结构性能的问题。通过动态规划的方法，计算量则圆圆小于一般的解法。原因在于，对于重叠子问题，一般情况下会被重复计算，而动态规划则是将重复的计算简化为计算一次就放入结果表中，在下一次计算时则从结果表中查询，从而直接获得结果，因此使性能得到提升。
动态规划与分治法类似，也是将问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。分治法在问题较大且相互不独立的情况下，由于分解得到的子问题数目太多，各个递归子问题被重复计算多次，求解过程呈幂级数增长，其时间复杂度为n的指数时间。与分治法不同，动态规划方法采用自底向上的递推方式求解，并且经分解得到的子问题往往不是相互独立的，根据子问题的相关性，在每步列出可能的局部解中选出能产生最佳解的部分，并将计算过程填表，只要某个子问题被解决,将不会被多次计算，从而减少了算法的时间复杂度。
动态规划建立在最优原则的基础上，在每一步决策上列出各种可能的局部解，按某些条件舍弃肯定不能得到最优解的局部解，通过逐步筛选，减少计算量。依据最优性原理，寻找最优判断序列，不论初始状态如何，下一次决策必须相对前一次决策产生的新状态构成最优序列。每一步都经过筛选，以每一步的最优性来保证全局的最优性。
动态规划是从初始状态计算结果，后续的计算都依赖于前一个计算结果状态，最终获得解的过程。主要过程包括如下：
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。实际应用中可以按以下几个简化的步骤进行设计：
能采用动态规划求解的问题的一般要具有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算法等。由于涉及到的内容较多，后续的文章中再做分享。
The post 常用算法之动态规划法 appeared first on 标点符.
Related posts: