详解动态规划算法
摘要
动态规划（dynamic programming，简称dp)是⼯程中⾮常重要的解决问题的思想，从我们在⼯程中地图软件上应⽤的最短路径问题，再在⽣活中的在淘宝上如何凑单以便利⽤满减券来最⼤程度地达到我们合理薅⽺⽑的⽬的，很多时候都能看到它的⾝影。不过动态规划对初学者来说确实⽐较难，dp状态，状态转移⽅程让⼈摸不着头脑，⽹上很多⼈也反馈不太好学，其实就像我们之前学递归那样，任何算法的学习都是有它的规律和套路的，只要掌握好它的规律及解题的套路，再加上⼤量的习题练习，相信掌握它不是什么难事，本⽂将会⽤⽐较浅显易懂地讲解来帮助⼤家掌握动态规划这⼀在⼯程中⾮常重要的思想，相信看完后，动态规划的解题套路⼀定能⼿到擒来（⽂章有点长，建议先收藏再看，看完后⼀定会对动态规划的认知上升到⼀个台阶！）
本⽂将会从以下⾓度来讲解动态规划：
什么是动态规划
动态规划从⼊门到进阶
法国的英语怎么说再谈动态规划
什么是动态规划
以下是我综合了动态规划的特点给出的动态规划的定义：动态规划是⼀种多阶段决策最优解模型，⼀般⽤来求最值问题，多数情况下它可以采⽤⾃下⽽上的递推⽅式来得出每个⼦问题的最优解（即最优⼦结构），进⽽⾃然⽽然地得出依赖⼦问题的原问题的最优解。
划重点：
什么不倦多阶段决策，意味着问题可以分解成⼦问题，⼦⼦问题，。。。，也就是说问题可以拆分成多个⼦问题进⾏求解
读报参考最优⼦结构，在⾃下⽽上的递推过程中，我们求得的每个⼦问题⼀定是全局最优解，既然它分解的⼦问题是全局最优解，那么依赖于它们解的原问题⾃然也是全局最优解。
⾃下⽽上，怎样才能⾃下⽽上的求出每个⼦问题的最优解呢，可以肯定⼦问题之间是有⼀定联系的，即迭代递推公式，也叫「状态转移⽅程」，要定义好这个状态转移⽅程， 我们就需要定义好每个⼦问题的状态（DP 状态），那为啥要⾃下⽽上地求解呢，因为如果采⽤像递归这样⾃顶向下的求解⽅式，⼦问题之间可能存在⼤量的重叠，⼤量地重叠⼦问题意味着⼤量地重复计算，这样时间复杂度很可能呈指数级上升（在下⽂中我们会看到多个这样重复的计算导致的指数级的时间复杂度），所以⾃下⽽上的求解⽅式可以消除重叠⼦问题。
简单总结⼀下，最优⼦结构，状态转移⽅程，重叠⼦问题就是动态规划的三要素，这其中定义⼦问题的状态与写出状态转移⽅程是解决动态规划最为关键的步骤，状态转移⽅程如果定义好了，解决动态规划就基本不是问题了。
既然我们知道动态规划的基本概念及特征，那么怎么判断题⽬是否可以⽤动态规划求解呢，其实也很简单，当问题的定义是求最值问题，且问题可以采⽤递归的⽅式，并且递归的过程中有⼤量重复⼦问题的时候，基本可以断定问题可以⽤动态规划求解，于是我们得出了求解动态规划基本思路如下（解题四步曲）
判断是否可⽤递归来解，可以的话进⼊步骤 2
分析在递归的过程中是否存在⼤量的重复⼦问题
采⽤备忘录的⽅式来存⼦问题的解以避免⼤量的重复计算（剪枝）
改⽤⾃底向上的⽅式来递推，即动态规划
接下来我们会做⼏道习题来强化⼀下⼤家对这些概念及动态规划解题四步曲的理解，每道题我们都会分别⽤递归，递归+备忘录，动态规划来求解⼀遍；
动态规划从⼊门到进阶
⼊门题：斐波那契数列
武汉英语学校接下来我们来看看怎么⽤动态规划解题四步曲来解斐波那契数列小兔子手工
画外⾳：斐波那契数列并不是严格意义上的动态规划，因为它不涉及到求最值，⽤这个例⼦旨在说明重叠⼦问题与状态转移⽅程
1、判断是否可⽤递归来解 显然是可以的，递归代码如下
public static int fibonacci (int n ) {
if (n == 1) return1;
if (n == 2) return2;美轮美奂造句
return fibonacci (n - 1) + fibonacci (n - 2);
}
2、分析在递归的过程中是否存在⼤量的重复⼦问题
怎么分析是否有重复⼦问题，画出递归树
可以看到光是求 f(6)，就有两次重复的计算， f(4) 求解了两次，f(3) 求解了两次，时间复杂度是指数级别，递归时间复杂度怎么看，解决每个⼦问题需要的时间乘以⼦问题总数，每个⼦问题需要的时间即 f(n) = f(n-1) + f(n-2) 只做了⼀次加法运算，⼦问题的个数有多少呢，每个问题⼀分为⼆，是个⼆叉树，可以看到第⼀层 1 个，第⼆层 2 个，第三层 4 个，即 1 + 2 + 2^2 + … 2n)，是指数级别。
画外⾳：求解问题 f(6)，转成求 f(5),f(4)，从原问题出发，分解成求⼦问题，⼦问题再分解成⼦⼦问题，。。。，直到再也不能分解，这种从原问题展开⼦问题进⾏求解的⽅式叫⾃顶向下
3、采⽤备忘录的⽅式来存⼦问题的解以避免⼤量的重复计算 既然以上中间⼦问题中存在着⼤量的重复计算，那么我们可以把这些中间结果给缓存住（可以⽤哈希表缓存），如下
public static int fibonacci (int n ) {
if (n = 1) return1;
if (n = 2) return2;
if (map .get (n ) != null ) {
return map .get (n );
}
int result = fibonacci (n - 1) + fibonacci (n - 2);
map .put (n , result );
return result ;
}
n，所以总的来说时间复杂度是)O(2
这么缓存之后再看我们的递归树
可以看到通过缓存中间的数据，做了⼤量地剪枝的⼯作，同样的f(4),f(3),f(2)，都只算⼀遍了，省去了⼤量的重复计算，问题的规模从⼆叉树变成了单链表（即 n），时间复杂度变成了 O(n)，不过由于哈希表缓存了所有的⼦问题的结果，空间复杂度是 O(n)。
4、改⽤⾃底向上的⽅式来递推，即动态规划 我们注意到如下规律
f(1)=1
f(2)=2
f(3)=f(1)+f(2)=3
f(4)=f(3)+f(2)=5
....
f(n)=f(n-1)+f(n-2)
所以只要依次⾃底向上求出 f(3),f(4),…,⾃然⽽然地就求出了 f(n)
画外⾳：从最终地不能再分解的⼦问题根据递推⽅程（f(n) = f(n-1) + f(n-2)）逐渐求它上层的问题，上上层问题，最终求得⼀开始的问题，这种求解问题的⽅式就叫⾃底向上。
f(n) 就是定义的每个⼦问题的状态（DP 状态），f(n) = f(n-1) + f(n-2) 就是状态转移⽅程，即 f(n) 由 f(n-1), f(n-2) 这两个状态转移⽽来，由于每个⼦问题只与它前⾯的两个状态，所以我们只要定义三个变量，⾃底向上不断循环迭代即可，如下
public int f(int n){
if(n ==1) return1;
if(n ==2) return2;
int result =0;
int pre =1;
int next =2;
for(int i =3; i < n +1; i ++){
result = pre + next;
pre = next;
next = result;
}
return result;
}
这样时间复杂度虽然还是O(n)，但空间复杂度只由于只定义了三个变量（result,pre,next）所以是常量 O(1)。
通过简单地斐波那契的例⼦，相信⼤家对⾃底向上，DP 状态， DP 转移⽅程应该有了⽐较深⼊地认识，细⼼的同学⼀定发现了最优⼦结构怎么没有，因为前⾯我们也说了，斐波那契数列并不是严格意义上的动态规划，只是先⽤这个简单地例⼦来帮助⼤家了解⼀下⼀些基本的概念。在之后的习题中我们将会见识到真正的动态规划
⼩试⽜⼑：三⾓形的最⼩路径和
如图⽰，以上三⾓形由⼀连串的数字构成，要求从顶点 2 开始⾛到最底下边的最短路径，每次只能向当前节点下⾯的两个节点⾛，如 3 可以向 6 或 5 ⾛，不能直接⾛到 7。
如图⽰：从 2 ⾛到最底下最短路径为 2+3+5+1 = 11，即为我们所求的
⾸先我们需要⽤⼀个⼆维数组来表⽰这个三个⾓形的节点，⽤⼆维数组显然可以做到， 第⼀⾏的 2 ⽤ a[0][0] 表⽰，第⼆⾏元素 3, 4 ⽤a[1][0],a[1][1]，依此类推。
期中反思
求余定义好数据结构之后，接下来我们来看看如何套⽤我们的动态规划解题套路来解题
1、 判断是否可⽤递归来解
如果⽤递归，就要穷举所有的路径和，最后再求所有路径和的最⼩值，我们来看看⽤递归怎么做。
对于每个节点都可以⾛它的左或右节点，假设我们定义 traver(i, j) 为节点 a[i][j] 下⼀步要⾛的节点，则可以得出递归公式的伪代码如下
traver(i, j)={
traver(i+1, j)；向节点i,j 下⾯的左节点⾛⼀步
traver(i+1, j+1)；向节点i,j 下⾯的右节点⾛⼀步
}
什么时候终⽌呢，显然是遍历到三⾓形最后⼀条边的节点时终⽌，发现了吗，对每个节点来说，在往下（⽆论是往左还是往右）遍历的过程中，问题规模不断地在缩⼩，也有临界条件（到达最后⼀条边的节点时终⽌），分解的⼦问题也有相同的解决问题的思路（对于每个节点的遍历都是往左或往右），符合递归的条件！于是我们得到递归代码如下
