代码急转弯——什么是动态规划

代码急转弯——动态规划最简描述

1、递归2、备忘录3、计算顺序 动态规划是解决计算问题的基本方法。它与递归非常相似，但又有所不同。下面以斐波那契哦数列的计算来说明动态规划的基本思想。

1、递归

斐波那契数列指的是 $x_0=1$ $x_1=1$ $x_n=x_{n-1}+x_{n-2},n=3,4,5,...$ 如果果要计算 f(10)，需要先计算出 f(8) 和 f(9)，然后就能由 f(8)+f(9) 计算得到 f(10) 了。

def feibonaci(n): if n == 1: return 1 if n == 2: return 1 return feibonaci(n-1) + feibonaci(n-2) print(feibonaci(30))

2、备忘录

递归代码有计算效率的问题。计算 f(10) 的时候，需要先计算 f(8) 和 f(9)，为了计算 f(9)，还必须计算 f(7) 和 f(8)，显然，计算了两遍 f(8)。类似地，为了计算 f(7) 和 f(8)，又得多次计算 f(6)。为了提高计算效率，可以采用备忘录算法，在第一次计算出 f(6) 时，将它存储起来，当需要再次计算 f(6)，以查表来替代计算，来换取更高的效率。

hs = {} def feibonaci(n): if n == 1: return 1 if n == 2: return 1 if n in hs: return hs[n] res = feibonaci(n-1) + feibonaci(n-2) hs[n] = res return res print(feibonaci(30))

3、计算顺序

为递归添上了备忘录，距离动态规划还有一步之遥。毕竟，用hs存储历史信息要花费不小的空间，能不能缩减所要的空间？就计算过程来看，hs[1]只用于计算 f(2) 和 f(3)，而与计算 f(4)、f(5)等无关。所以，调整一下计算顺序，按照 n 从小到大的顺序来计算 f(n)，就能减少hs占用的空间。

def feibonaci(n): if n == 1: return 1 if n == 2: return 1 hs1 = 1 hs2 = 1 for i in range(3, n): hs1, hs2 = hs2, hs1 + hs2 return hs1 + hs2 print(feibonaci(30))

当然，不是所有的问题都能如此简化，但是消除递归依旧能提高运行效率。 总结下，动态规划就是大事化小，小事化了，用查表替代计算，改变顺序消除递归。