画外音：从一个最终无法再分解的子问题，按照递归方程(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)两个状态转移而来，因为每个子问题只与它之前的两个状态相关，

(intn){ if(n==1)；if(n==2)；=0;=1;=2;for(inti=3；在1；I){=pre next；pre=nextnext=；};}

这样，虽然时间复杂度仍然是O(n)，但是空间复杂度是常数O(1)，因为只定义了三个变量(结果，pre，next)。

通过一个简单的斐波那契例子，相信大家应该对自下而上、DP状态、DP跃迁方程有更深入的了解。细心的同学一定要搞清楚为什么没有最优子结构，因为我们前面说过，斐波那契序列不是严格意义上的动态规划，就用这个简单的例子来帮助你理解一些基本概念。在下面的练习中，我们将看到真正的动态规划

尽力而为：三角形的最小路径和

如图，上面的三角形是由一系列数字组成的，需要从顶点2到底边的最短路径，一次只能到当前节点下面的两个节点。比如3可以去6或者5，但是不能直接去7。

如图：所示，从2到底部的最短路径是2 ^ 3 ^ 5 ^ 1=11，这就是我们想要的

首先，我们需要用一个二维数组来表示三个角的节点。显然，这可以通过使用二维数组来完成，其中第一行中的2由[0][0]表示，第二行中的元素3和4由[1][0]、a[1][1]等表示。

在定义了数据结构之后，让我们看看如何应用我们的动态编程问题解决例程来解决问题

1.确定递归是否可以用来解决问题

如果用递归的话，一定要穷尽所有路径和，最后找到所有路径和的最小值。让我们看看如何使用递归。

每个节点都可以走自己的左节点或右节点。假设我们将traverse(i，j)定义为节点a[i][j]的下一个节点，我们可以得到如下递归公式的伪代码

traverse(i，j)={traverse(i，j 1)；在节点I和J(I ^ 1，J ^ 1)下面向左节点走一步；向节点I和J下方的右侧节点迈出一步}

什么时候终止？显然，当遍历到三角形最后一条边的节点时，就会终止。你有没有发现，对于每个节点，问题的规模在向下遍历(无论是左还是右)的过程中不断缩小，也存在临界条件(到达最后一条边的节点时终止)。分解后的子问题也有同样的求解思路(对于每个节点都是向左或向右遍历)，满足递归条件。所以我们得到如下递归代码

private stat int[][]三角形=；publicationstatinttraverse(inti，intj){ inttotalRow=4；//总行数if(I=TotalRow-1){ return 0；}//走到左下节点时，intleft sum=traverse(I ^ 1，j)三角形[I ^ 1][j]；//走到右下节点时，intrightsum=traverse(I ^ 1，J ^ 1)三角形[I ^ 1][J ^ 1]；//记录每个节点向左和向右遍历的路径之和的最小值(leftsum，right sum)；} public static void main(String[]args)throwStrowable { int sum=traverse(0，0)三角形[0][0]；system . out . println(sum=sum)；}

时间复杂度如何？从下面的伪代码可以看出

traverse(i，j)={traverse(i，j 1)；在节点I和J(I ^ 1，J ^ 1)下面向左节点走一步；向节点I和J下方的右侧节点迈出一步}

对于每个节点，无论是左还是右，每个问题都被分解成两个子问题。像斐波那契数列，如果画递归树，也是二叉树，那么时间复杂度是O (2 n)，也是指数的。

2.分析递归过程中是否有大量重复的子问题

为什么时间复杂度是指数级的？先简单分析一下：

对于节点3和4，如果节点3向右遍历，节点4向左遍历，两者都到达节点5，如果节点5向下遍历，它将遍历两次，因此此时将有重复的子问题

3.Memo用于保存问题的解决方案，避免大量重复计算(剪枝)

现在它出现了，我们将用备忘录缓存中间节点

因此，我们的代码更改如下

private stat int[][]三角形=；//记录中间状态的mapprivatestatichashmapstring，integermap=new hashmap()；publicationstatinttraverse(inti，intj){ Stringkey=I j；if(map.get(key)！=null){ return map . get(key)；} inttotalRow=4；//总行数，如果

(i=totalRow-1){return0;}//往左下节点走时intleftSum=traverse(i+1,j)+triangle[i+1][j];//往右下节点走时intrightSum=traverse(i+1,j+1)+triangle[i+1][j+1];//记录每个节点往左和往右遍历的路径和的最小值intresult=Math.min(leftSum,rightSum);map.put(key,result);returnresult;}

这么一来，就达到了剪枝的目的，避免了重复子问题，时间复杂度一下子下降到O(n),空间复杂度呢，由于我们用哈希表存储了所有的节点的状态，所以空间复杂度是O(n)。

4、改用自底向上的方式来递推，即动态规划

重点来了，如何采用自底向上的动态规划来解决问题呢?我们这么来看，要求节点2到底部边的最短路径，只要先求得节点3和节点4到底部的最短路径值，然后取这两者之中的最小值再加2不就是从2到底部的最短路径了吗，同理，要求节点3或节点4到底部的最小值，只要求它们的左右节点到底部的最短路径再取两者的最小值再加节点本身的值（3或4）即可。

我们知道对于三角形的最后一层节点，它们到底部的最短路径就是其本身，于是问题转化为了已知最后一层节点的最小值怎么求倒数第二层到最开始的节点到底部的最小值了。先看倒数第二层到底部的最短路径怎么求

同理，第二层对于节点3，它到最底层的最短路径转化为了3到7，6节点的最短路径的最小值，即9,对于节点4，它到最底层的最短路径转化为了4到6，10的最短路径两者的最小值，即10。

接下来要求2到底部的路径就很简单了，只要求2到节点9与10的最短路径即可，显然为11。

于是最终的11即为我们所求的值，接下来我们来看看怎么定义DP的状态与状态转移方程。我们要求每个节点到底部的最短路径，于是DP状态DP[i,j]定义为i,j的节点到底部的最小值，DP状态转移方程定义如下：

DP[i,j]=min(DP[i+1,j],D[i+1,j+1])+triangle[i,j]

这个状态转移方程代表要求节点到最底部节点的最短路径只需要求左右两个节点到最底部的最短路径两者的最小值再加此节点本身！仔细想想我们上面的推导过程是不是都是按这个状态转移方程推导的，实在不明白建议多看几遍上面的推导过程，相信不难明白。

DP状态DP[i,j]有两个变量，需要分别从下而上，从左到右循环求出所有的i,j,有了状态转移方程求出代码就比较简单了，如下

privatestaticint[][]triangle=;publicstaticinttraverse(){intROW=4;int[]mini=triangle[ROW-1];//从倒数第二行求起，因为最后一行的值本身是固定的for(inti=ROW-2;i=0;i--){for(intj=0;jtriangle[j].length;j++){mini[j]=triangle[i][j]+Math.min(mini[j],mini[j+1]);}}returnmini[0];}publicstaticvoidmain(String[]args)throwsThrowable{intminPathSum=traverse();System.out.println(sum=+minPathSum);}

可能有一些人对mini数组的定义有疑问，这里其实用了一个比较取巧的方式，首先我们定义mini的初始值为最后一行的节点，因为最后一行的每个节点的DP[i,j]是固定值，只要从倒数第二行求起即可，其次我们知道每个节点到底部的最短路径只与它下一层的D[I+1,j],D[i+1,j]有关，所以只要把每一层节点的DP[i,j]求出来保存到一个数组里即可，就是为啥我们只需要定义一下mini一维数组的原因

如图示：要求节点2到底部的最短路径，它只关心节点9，10，之前层数的节点无需再关心！因为9，10已经是最优子结构了，所以只保存每层节点（即一维数组）的最值即可！

当自下而上遍历完成了，mini[0]的值即为DP[0,0],即为节点2到底部的最短路径。mini的定义可能有点绕，大家可以多思考几遍，当然，你也可以定义一个二维数组来保存所有的DP[i,j]，只不过多耗些空间罢了。

这里我们再来谈谈最优子结构，在以上的推导中我们知道每一层节点到底部的最短路径依赖于它下层的左右节点的最短路径，求得的下层两个节点的最短路径对于依赖于它们的节点来说就是最优子结构，最优子结构对于子问题来说属于全局最优解，这样我们不必去求节点到最底层的所有路径了，只需要依赖于它的最优子结构即可推导出我们所要求的最优解，所以最优子结构有两层含义，一是它是子问题的全局最优解，依赖于它的上层问题只要根据已求得的最优子结构推导求解即可得全局最优解，二是它有缓存的含义，这样就避免了多个依赖于它的问题的重复求解（消除重叠子问题）。

总结：仔细回想一下我们的解题思路，我们先看了本题是否可用递归来解，在递归的过程中发现了有重叠子问题，于是我们又用备忘录来消除递归中的重叠子问题，既然我们发现了此问题可以用递归+备忘录来求解，自然而然地想到它可以用自底向上的动态规划来求解。是的，求解动态规划就按这个套路来即可，最重要的是要找出它的状态转移方程，这需要在自下而上的推导中仔细观察。

进阶：凑零钱

给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。输入:coins=[1,2,5],amount=11，输出:3解释:11=5+5+1输入:coins=[2],amount=3，输出:-1

来套用一下我们的动态规划解题四步曲

一、判断是否可用递归来解

对于amount来说，如果我们选择了coins中的任何一枚硬币，则问题的规模(amount)是不是缩小了,再对缩小的amount也选择coins中的任何一枚硬币,直到再也不能选择（amount=0,amount=0代表有符合条件的解，小于0代表没有符合条件的解），从描述中我们可以看出问题可以分解成子问题，子问题与原问题具有相同的解决问题的思路，同时也有临界条件，符合递归的条件，由此可证可以用递归求解，接下来我们来看看，如何套用递归四步曲来解题

1、定义这个函数，明确这个函数的功能,函数的功能显然是给定一个amount，用定义好的coins来凑，于是我们定义函数如下

privatestaticintf(intamount,int[]coins){}

2、寻找问题与子问题的关系，即递推公式这题的递推关系比较难推导，我们一起看下，假设f(amount,coins)为零钱amount的所需要的最少硬币数，当选中了coins中的第一枚硬币之后（即为coins[0]），则需再对剩余的amount-coins[0]金额求最少硬币数，即调用f(amount-coins[0],coins),由此可知当选了第一枚硬币后的递推公式如下

f(amount,coins)=f(amount-coins[0])+1(这里的1代表选择了第一枚硬币)

如果选择了第二，第三枚呢，递推公式如下

f(amount,coins)=f(amount-coins[1])+1(这里的1代表选择了第二枚硬币)f(amount,coins)=f(amount-coins[2])+1(这里的1代表选择了第三枚硬币)

我们的目标是求得所有以上f(amount,coins)解的的最小值，于是可以得到我们的总的递推公式如下

f(amount,coins)=min{f(amount-coins[i])+1)},其中i的取值为0到coins的大小，coins[i]表示选择了此硬币,1表示选择了coins[i]这一枚硬币

3、将第二步的递推公式用代码表示出来补充到步骤1定义的函数中

得出了递推公式用代码实现就简单了，来简单看一下

publicclassSolution{privatestaticintexchange(intamount,int[]coins){//说明零钱刚好凑完if(amount==0){return0;}//说明没有满足的条件if(amount0){return-1;}intresult=Integer.MAX_VALUE;for(inti=0;icoins.length;i++){intsubMin=exchange(amount-coins[i],coins);if(subMin==-1)continue;result=Math.min(subMin+1,result);}//说明没有符合问题的解if(result==Integer.MAX_VALUE){return-1;}returnresult;}publicstaticvoidmain(String[]args)throwsThrowable{intamount=11;int[]coins={1,2,5};intresult=exchange(amount,coins);System.out.println(result=+result);}}

4、计算时间复杂度这道题的时间复杂度很难看出来，一般看不出来的时候我们可以画递归树来分析，针对amount=11的递归树如下

前文我们说到斐波那契的递归树是一颗二叉树，时间复杂度是指数级别，而凑零钱的递归树是一颗三叉树，显然时间复杂度也是指数级别!

二、分析在递归的过程中是否存在大量的重叠子问题（动态规划第二步）

由上一节的递归树可知，存在重叠子问题，上一节中的9，8，都重复算了,所以存在重叠子问题！

三、采用备忘录的方式来存子问题的解以避免大量的重复计算（剪枝）

既然我们知道存在重叠子问题，那么就可以用备忘录来存储中间结果达到剪枝的目的

publicclassSolution{//保存中间结果privatestaticHashMapInteger,Integermap=newHashMap();//带备忘录的递归求解privatestaticintexchangeRecursive(intamount,int[]coins){if(map.get(amount)!=null){returnmap.get(amount);}//说明零钱已经凑完if(amount==0){return0;}//说明没有满足的条件if(amount0){return-1;}intresult

标签： #动态规划最新问题