斐波那契数列是由0和1开始，之后的数就是前两个数的和。
首几个费波那契系数是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
那我们如何用计算机来生成这些数呢，也就是说，求斐波那契数列第n位的值。
很简单，用递归就可以了：

# 自上而下地递归
def fib(n):if n in [0,1]:return nreturn fib(n-1) + fib(n-2)print(fib(10))

输出： 55

• 1

结果没有问题，接下来看一下递归性能如何。

写个简单的计时的测试代码：

import time
n = 40
tic = time.clock()
res = fib(n)
toc = time.clock()
print('fib({}) = {}'.format(n,res))
print('runtime: {}s '.format(toc-tic))

我们看下n=10的结果：

fib(10) = 55
runtime: 2.4462208330078283e-05s 

再看下 n=40 时的结果：

fib(40) = 102334155
runtime: 40.73219172568648s 

我们发现：当n变大时，这段递归代码用时变得很久，而且性能是急剧下降。这是为什么呢？

拿fib(5)来举例，要计算fib(5)，得知道fib(4)的值，要计算fib(4)的值，又得知道fib(3)的值，以此类推，直到递归到底时，fib(0)=0。下图是个fib(5)求解的展开图，可以看到，这里面有很过的重复计算，比如浅粉色框框住的fib(2)就重复计算了三次，可想而知当n很大时，这些重复计算的次数将呈指数上升，这就是递归效率不高的原因——重叠子问题。

改进方法就是，将计算过的fib()值存储下来，下次用到直接查就行，这种方法叫记忆化搜索。
于是在递归代码的基础上可以很轻松地改写成记忆化搜索，代码如下：

# 记忆化搜索：自上而下地求解
def fib_memo(n):def fib(n):if n in [0,1]:return n# 如果memo数组中没有计算过fib(n)，则需计算一下并存到memo[n]中if memo[n] == -1:memo[n] = fib(n-1) + fib(n-2)return memo[n]memo = [-1 for i in range(n+1)]  # memo[0...n]中所有元素初始值为-1，表示未计算return fib(n)

fib(40)的测试结果：

fib(40) = 102334155
runtime: 2.4746652798057767e-05s 

经过简单的记忆化改造，效率由 40.7s 提升到了 0.0000247s ！
记忆化搜索本质还是一种递归，只是用额外的变量来存储中间值而已，属于典型的空间换时间的方式。由于递归是一种自顶向下的方式，所以记忆化搜索也是一种自顶而下的搜索方法，即计算顺序是

   fib(n) → fib(n-1) → fib(n-2) → ... → fib(1) → fib(0)

最后再从fib(0)一路回溯给fib(n)，done！

那么可不可以自底向上地算出斐波那契数列呢？当然有啊，这就是接下来要隆重请出的动态规划。

思路很简单，知道了 fib(0) 和 fib(1)，就可以相加得fib(2)，fib(1)+fib(2)又得fib(3)，依次类推直到 fib(n)。自底向上的求解过程：

   fib(0) → fib(1) → fib(2) → ... → fib(n-1) → fib(n)

没错，这也极其符合人的直观感觉，看着很舒服很顺眼。
于是很容易写出代码：

# 动态规划：自下而上地解决问题
def fib(n):memo = [-1 for i in range(n+1)]memo[0] = 0memo[1] = 1for i in range(2,n+1):memo[i] = memo[i-1] + memo[i-2]return memo[n]

看下测试结果：

fib(40) = 102334155
runtime: 1.6782212696853094e-05s 

0.0000167s 比记忆化搜索的 0.0000247s 又提高了一丢丢，这主要是因为记忆化搜索中多出了反复递归的开销。

其实fib数列不是重点，重点是这个：这里面fib(2)是fib(3)的子问题，fib(3)又是fib(4)的子问题，以此类推，所以这是一个通过子问题推得原问题的过程。我们可以把上面的过程总结为这句话：通过求子问题的最优解，可以获得原问题的最优解。
这里的子问题称为最优子结构。
好，接下类引出动态规划的定义：

将原问题拆解成若干个子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

好，介绍完毕。

在递归问题中如果存在重叠子问题，那么就可以进行以下两种改造：

1. 自顶而下地解决问题：记忆化搜索
2. 自底而上地解决问题：动态规划
   

前面我们将动态规划描述为一种 通过求子问题的最优解，从而求得原问题的最优解 的方法，那么有人可能会问了：

1. 如何将原问题切分成子问题？
2. 又怎么将子问题的解延伸回原问题，也就是说子问题和原问题是怎么连接起来的？

对于问题1，如何切分子问题，在DP中被称为状态的定义，其中子问题被称为状态。
对于问题2:，如何从子问题到原问题，在DP被称为状态转移方程。

这两个东西才是动态规划的核心。

到底是怎么回事，直接拿LeetCode上两个例子说话：

解析：

1. 我们定义 v[n] 分割正数n的最大乘积 ，这是状态的定义。
2. 每次将n分解为两个数的和，如：1+(n-1), 2+(n-2), 3+(n-3)…，对于每一种分割 i+(n-i)，最大乘积 v[n] 的来源于 i 和 n-i 的乘积 和 i 和 v[n-i] 的乘积 中较大的那个，而最终的最大v[n]是在所有 1<=i<=n上最大的那个，即v[n] = max( i×(n-i), i×v[n-i] ) for 1<=i<=n-1 ，这就是从v[n-1] 到 v[n] 的状态转移方程。
3. 这里存在重叠子问题，如下图中蓝块。
   
   思路： 递归、记忆化搜索、动态规划

1. 状态定义： v[n] 分割正数n的最大乘积
2. 状态转移： v[n] = max( i×(n-i), i×v[n-i] ) for 1<=i<=n-1

代码
我将递归、记忆化搜索和动态规划三种方法放在了一个类中：

class Solution:def integerBreak_rec(self, n):""":type n: int:rtype: int原生的递归方法：效率低"""def breakInteger(n):if n==1:return 1res = -1for i in range(1,n):# n = i + (n-i)res = max( res, i*(n-i), i*breakInteger(n-i) )return resreturn breakInteger(n)def integerBreak_memo(self, n):""":type n: int:rtype: int第一种改进： 自上而下的记忆化搜索"""def breakInteger(n):if n==1:return 1if memo[n] != -1:return memo[n]res = -1for i in range(1,n):# n = i + (n-i)res = max( res, i*(n-i), i*breakInteger(n-i) )memo[n] = resreturn resassert n>=2memo = [-1 for i in range(n+1)]return breakInteger(n)def integerBreak_dp(self, n):""":type n: int:rtype: int第二种改进：自底向上动态规划"""assert n>=2memo = [-1 for i in range(n+1)]memo[1] = 1for i in range(2,n+1):for j in range(1,i):memo[i] = max( memo[i], j*(i-j), j*memo[i-j] )return memo[n]if __name__ == '__main__':      n = Solution().integerBreak_dp(10)print(n)

LeetCode上与此题相似的题目：

• 279 Perfect Squares
  给定一格正整数n，寻找最少的完全平方数，使他们的和为n。
• 91 Decode Ways
  数字字符串的解析
• 62 Unique Paths
  机器人从m×n的矩阵左上角出发到达右下角（每次只能向右或向下），共有多少种路径？
• 63 Unique Paths II
  （接上题）若矩阵中含有障碍物，此时共有多少种路径？

小偷洗劫一条街上的所有房子，每个房子有不同价值的把宝物，但不能连续抢劫俩相邻房子。求最多可以偷到多少宝物？

在动态规划中，有类非常经典的问题称为0-1背包问题。有一个背包，容量是C，现有那种不同的物品，编号为0…n-1
，其中每一件物品重量为w(i),价值为v(i)。问可以向包中放哪些物品，使得在不超过背包容量的基础上，物品总价值最大。

暴力解法：每一件物品都可以放进或者不放进，遍历所有可能性。 时间复杂度O((2^n)*n)。
贪心算法：优先放入平均价值最大的物品，结果只是近似解，而不是最优解。
动态规划：

状态： F(n,C) 考虑将n个物品放进容量为C的背包，使得价值最大。(这里约束条件为n和C)
状态转移方程： F(i,C) = max( F(i-1,C), v(i)+F(i-1,C-w(i)) )
对应 1.不放入第i个物品 2.放入第i个物品 这两种状态中值最大的那个。

时间复杂度为O(nC)已经几乎没有优化空间了，但是可以从空间复杂度上进行优化。

1. 动态规划解法: n行版
   原始动态规划，建立一个n行C+1列的矩阵 memo[n-1][C+1]
   时间复杂度：O(nC)
   空间复杂度：O(nC)

2. 动态规划解法: 两行版
   改进1：由于第i行元素只依赖于第i-1行元素。理论上，memo只需要保证两行元素。
   空间复杂度 O(2C)=O( C)

3. 动态规划解法： 一行版
   改进2：由于某位置的元素只依赖于上一行的对应位置和上一行的左侧元素。所以可以从右边开始更新，这样memo只需一行就可以完成。
   空间复杂度 O( C)

• 多重背包问题：每个物品不止1个，有num(i)个
• 完全背包问题：每个物品可以无限使用
• 多维费用背包问题：要考虑物品的体积和重量两个维度（原问题上增加一个约束条件，memo数组变为三维即可）
• 物品间加入更多约束：物品间可以相互排斥；也可以相互依赖

416 Patition Equal Subset Sum 分割等和子集

典型的背包问题：在n个物品中选出一定物品，填满sum/2的背包
与原背包问题不同的是：我们不需要物品价值最大，目标是能填满。或者也可以理解为物品价值均为1。

给定一整数序列，求其中的最长上升子序列的长度。

• 方法1：动态规划解法
  1. 状态定义： LIS(i) 表示以第i个数字为结尾的最长上升子序列的长度。即表示[0…i]范围内，选择数组nums[i] 可以获得的最长上升子序列的长度
  2. 状态转移： LIS(i) = max( 1+LIS(j) if nums[i]>nums[j] for j<i )
  时间复杂度O(n^2)
• 方法2：二分搜索法
  这里不做介绍。
  时间复杂度O(nlogn)

LeetCode上与此题相似的题目：

• 376 Wiggle Subsequence
  求最长轮流交替子序列

给出两个字符串S1和S2，求这两个字符串的最长公共子序列的长度。
状态定义：

LCS(m,n) 是S1[0…m]和S2[0…n]的最长公共子序列的长度。

转移方程：

1. S1[m] == S2[n]： LCS(m,n) = 1+ LCS(m-1,n-1)
2. S1[m] != S2[n]： LCS(m,n) = max(LCS(m-1,n),LCS(m,n-1))

• 动态规划其实相当常见，譬如 dijkstra单源最短路径算法也是动态规划

  状态定义： shortestPath(i)为从start到i的最短路径长度
  状态转移： shortestPath(i) = min( shortestPath(i) + w(a->i))

• 动态规划是一个非常大的问题范畴，因为它不仅他可以解决的问题是非常灵活的，还因为它是公认的在算法设计上艺术含量非常高的算法，因为动态规划似乎没有一个固定的套路。
• LeetCode上更多关于动态规划的问题，找dp标签的题。
• 单论面试，面试中动态规划考察较少，更多的是考察更基础的问题，所以可以相对放松对LeetCode上动态规划题目的要求。

例1： 300. 最长上升子序列。
例2： 0-1背包问题

References：
非常好的动态规划总结，DP总结
背包问题的总结
动态规划（dp） 之 状态转移方程