前一篇博客总结了动态规划，但是对于我这初学者，还是很多地方不能理解，所以我就在网上找到了一个大神的讲解，确实很棒。转载过来。
原文链接在下面参考资料。
下面通过对斐波那契数列和这道凑零钱问题详解动态规划。如果只想看本题的答案，请直接翻到最后查看。
而且，当你去看用动态规划解决某个问题的代码时，你会觉得这样解决问题竟然如此巧妙，但却难以理解，你可能惊讶于人家是怎么想到这种解法的。
实际上，动态规划是一种常见的“算法设计技巧”，并没有什么高深莫测，至于各种高大上的术语，那是吓唬别人用的，只要你亲自体验几把，这些名词的含义其实显而易见，再简单不过了。
至于为什么最终的解法看起来如此精妙，是因为动态规划遵循一套固定的流程：递归的暴力解法->带备忘录的递归解法->非递归的动态规划解法。这个过程是层层递进的解决问题的过程，你如果没有前面的铺垫，直接看最终的非递归动态规划解法，当然会觉得牛逼而不可及了。
当然，见的多了，思考多了，是可以一步写出非递归的动态规划解法的。任何技巧都需要练习，我们先遵循这个流程走，算法设计也就这些套路，除此之外，真的没啥高深的。
首先，第一个快被举烂了的例子，斐波那契数列。请读者不要嫌弃这个例子简单，因为简单的例子才能让你把精力充分集中在算法背后的通用思想和技巧上，而不会被那些隐晦的细节问题搞的莫名其妙。后续，困难的例子有的是。
intfib(intN){if(N==1||N==2)return1;returnfib(N-1)+fib(N-2);}这个不用多说了，学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂，但是十分低效，低效在哪里？假设n=20，请画出递归树。
PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。
这个递归树怎么理解？就是说想要计算原问题f(20)，我就得先计算出子问题f(19)和f(18)，然后要计算f(19)，我就要先算出子问题f(18)和f(17)，以此类推。最后遇到f(1)或者f(2)的时候，结果已知，就能直接返回结果，递归树不再向下生长了。
子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为O(2^n)。
这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。
明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
intfib(intN){if(N<1)return0;//备忘录全初始化为0vectormemo(N+1,0);returnhelper(memo,N);}inthelper(vector&memo,intn){if(n==1||n==2)return1;if(memo[n]!=0)returnmemo[n];//未被计算过memo[n]=helper(memo,n-1)+helper(memo,n-2);returnmemo[n];}现在，画出递归树，你就知道「备忘录」到底做了什么。
实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是f(1),f(2),f(3)…f(20)，数量和输入规模n=20成正比，所以子问题个数为O(n)。
至此，带备忘录的递归解法的效率已经和动态规划一样了。实际上，这种解法和动态规划的思想已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。
啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说f(20)，向下逐渐分解规模，直到f(1)和f(2)触底，然后逐层返回答案，这就叫「自顶向下」。
啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的f(1)和f(2)开始往上推，直到推到我们想要的答案f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做DPtable吧，在这张表上完成「自底向上」的推算岂不美哉！
画个图就很好理解了，而且你发现这个DPtable特别像之前那个「剪枝」后的结果，只是反过来算而已。实际上，带备忘录的递归解法中的「备忘录」，最终完成后就是这个DPtable，所以说这两种解法其实是差不多的，大部分情况下，效率也基本相同。
这里，引出「动态转移方程」这个名词，实际上就是描述问题结构的数学形式：
为啥叫「状态转移方程」？为了听起来高端。你把f(n)想做一个状态n，这个状态n是由状态n-1和状态n-2相加转移而来，这就叫状态转移，仅此而已。
你会发现，上面的几种解法中的所有操作，例如returnf(n-1)+f(n-2)，dp[i]=dp[i-1]+dp[i-2]，以及对备忘录或DPtable的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。很容易发现，其实状态转移方程直接代表着暴力解法。
千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者DPtable，再无奥妙可言。
这个例子的最后，讲一个细节优化。细心的读者会发现，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个DPtable来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为O(1)：
intfib(intn){if(n<2)returnn;intprev=0,curr=1;for(inti=0;i有人会问，动态规划的另一个重要特性「最优子结构」，怎么没有涉及？下面会涉及。斐波那契数列的例子严格来说不算动态规划，以上旨在演示算法设计螺旋上升的过程。当问题中要求求一个最优解或在代码中看到循环和max、min等函数时，十有八九，需要动态规划大显身手。
下面，看第二个例子，凑零钱问题，有了上面的详细铺垫，这个问题会很快解决。
题目：给你k种面值的硬币，面值分别为c1,c2…ck，再给一个总金额n，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，则回答-1。
比如说，k=3，面值分别为1，2，5，总金额n=11，那么最少需要3枚硬币，即11=5+5+1。下面走流程。
一、暴力解法首先是最困难的一步，写出状态转移方程，这个问题比较好写：
其实，这个方程就用到了「最优子结构」性质：原问题的解由子问题的最优解构成。即f(11)由f(10),f(9),f(6)的最优解转移而来。
记住，要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。
比如说，你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…当然，最终就是你每门课都是满分，这就是最高的总成绩。
得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。
回到凑零钱问题，显然子问题之间没有相互制约，而是互相独立的。所以这个状态转移方程是可以得到正确答案的。
之后就没啥难点了，按照方程写暴力递归算法即可。
intcoinChange(vector&coins,intamount){if(amount==0)return0;intans=INT_MAX;for(intcoin:coins){//金额不可达if(amount-coin<0)continue;intsubProb=coinChange(coins,amount-coin);//子问题无解if(subProb==-1)continue;ans=min(ans,subProb+1);}returnans==INT_MAX-1:ans;}画出递归树：
二、带备忘录的递归算法
三、动态规划
最后总结如果你不太了解动态规划，还能看到这里，真得给你鼓掌，相信你已经掌握了这个算法的设计技巧。
计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
但是智力题终究是智力题，真正的算法问题肯定不会是投机取巧能搞定的。所以，本文就借石头游戏来讲讲「假设两个人都足够聪明，最后谁会获胜」这一类问题该如何用动态规划算法解决。
博弈类问题的套路都差不多，下文举例讲解，其核心思路是在二维dp的基础上使用元组分别存储两个人的博弈结果。掌握了这个技巧以后，别人再问你什么俩海盗分宝石，俩人拿硬币的问题，你就告诉别人：我懒得想，直接给你写个算法算一下得了。
我们「石头游戏」改的更具有一般性：
你和你的朋友面前有一排石头堆，用一个数组piles表示，piles[i]表示第i堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。
石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。比如有三堆石头piles=[1,100,3]，先手不管拿1还是3，能够决定胜负的100都会被后手拿走，后手会获胜。
假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。比如上面那个例子，先手能获得4分，后手会获得100分，你的算法应该返回-96。
这样推广之后，这个问题算是一道Hard的动态规划问题了。博弈问题的难点在于，两个人要轮流进行选择，而且都贼精明，应该如何编程表示这个过程呢？
还是强调多次的套路，首先明确dp数组的含义，然后和股票买卖系列问题类似，只要找到「状态」和「选择」，一切就水到渠成了。
定义dp数组的含义是很有技术含量的，同一问题可能有多种定义方法，不同的定义会引出不同的状态转移方程，不过只要逻辑没有问题，最终都能得到相同的答案。
我建议不要迷恋那些看起来很牛逼，代码很短小的奇技淫巧，最好是稳一点，采取可解释性最好，最容易推广的设计思路。本文就给出一种博弈问题的通用设计框架。
介绍dp数组的含义之前，我们先看一下dp数组最终的样子：
下文讲解时，认为元组是包含first和second属性的一个类，而且为了节省篇幅，将这两个属性简写为fir和sec。比如按上图的数据，我们说dp[1][3].fir=10，dp[0][1].sec=3。
先回答几个读者可能提出的问题：
这个二维dptable中存储的是元组，怎么编程表示呢？这个dptable有一半根本没用上，怎么优化？很简单，都不要管，先把解题的思路想明白了再谈也不迟。
以下是对dp数组含义的解释：
dp[i][j].fir表示，对于piles[i...j]这部分石头堆，先手能获得的最高分数。dp[i][j].sec表示，对于piles[i...j]这部分石头堆，后手能获得的最高分数。举例理解一下，假设piles=[3,9,1,2]，索引从0开始dp[0][1].fir=9意味着：面对石头堆[3,9]，先手最终能够获得9分。dp[1][3].sec=2意味着：面对石头堆[9,1,2]，后手最终能够获得2分。我们想求的答案是先手和后手最终分数之差，按照这个定义也就是dp[0][n-1].fir-dp[0][n-1].secdp[0][n1].firdp[0][n1].sec，即面对整个piles，先手的最优得分和后手的最优得分之差。
写状态转移方程很简单，首先要找到所有「状态」和每个状态可以做的「选择」，然后择优。
根据前面对dp数组的定义，状态显然有三个：开始的索引i，结束的索引j，当前轮到的人。
dp[i][j][firorsec]其中：0<=i对于这个问题的每个状态，可以做的选择有两个：选择最左边的那堆石头，或者选择最右边的那堆石头。我们可以这样穷举所有状态：
n=piles.lengthfor0<=i上面的伪码是动态规划的一个大致的框架，股票系列问题中也有类似的伪码。这道题的难点在于，两人是交替进行选择的，也就是说先手的选择会对后手有影响，这怎么表达出来呢？
根据我们对dp数组的定义，很容易解决这个难点，写出状态转移方程：
dp[i][j].fir=max(piles[i]+dp[i+1][j].sec,piles[j]+dp[i][j-1].sec)dp[i][j].fir=max(选择最左边的石头堆,选择最右边的石头堆)#解释：我作为先手，面对piles[i...j]时，有两种选择：#要么我选择最左边的那一堆石头，然后面对piles[i+1...j]#但是此时轮到对方，相当于我变成了后手；#要么我选择最右边的那一堆石头，然后面对piles[i...j-1]#但是此时轮到对方，相当于我变成了后手。if先手选择左边:dp[i][j].sec=dp[i+1][j].firif先手选择右边:dp[i][j].sec=dp[i][j-1].fir#解释：我作为后手，要等先手先选择，有两种情况：#如果先手选择了最左边那堆，给我剩下了piles[i+1...j]#此时轮到我，我变成了先手；#如果先手选择了最右边那堆，给我剩下了piles[i...j-1]#此时轮到我，我变成了先手。根据dp数组的定义，我们也可以找出basecase，也就是最简单的情况：
这里需要注意一点，我们发现basecase是斜着的，而且我们推算dp[i][j]时需要用到dp[i+1][j]和dp[i][j-1]：
所以说算法不能简单的一行一行遍历dp数组，而要斜着遍历数组：
说实话，斜着遍历二维数组说起来容易，你还真不一定能想出来怎么实现，不信你思考一下？这么巧妙的状态转移方程都列出来了，要是不会写代码实现，那真的很尴尬了。。。
如何实现这个fir和sec元组呢，你可以用python，自带元组类型；或者使用C++的pair容器；或者用一个三维数组dp[n][n][2]，最后一个维度就相当于元组；或者我们自己写一个Pair类：
classPair{intfir,sec;Pair(intfir,intsec){this.fir=fir;this.sec=sec;}}然后直接把我们的状态转移方程翻译成代码即可，可以注意一下斜着遍历数组的技巧：
/*返回游戏最后先手和后手的得分之差*/intstoneGame(int[]piles){intn=piles.length;//初始化dp数组Pair[][]dp=newPair[n][n];for(inti=0;iright){dp[i][j].fir=left;dp[i][j].sec=dp[i+1][j].fir;}else{dp[i][j].fir=right;dp[i][j].sec=dp[i][j-1].fir;}}}Pairres=dp[0][n-1];returnres.fir-res.sec;}动态规划解法，如果没有状态转移方程指导，绝对是一头雾水，但是根据前面的详细解释，读者应该可以清晰理解这一大段代码的含义。
本文给出了解决博弈问题的动态规划解法。博弈问题的前提一般都是在两个聪明人之间进行，编程描述这种游戏的一般方法是二维dp数组，数组中通过元组分别表示两人的最优决策。
之所以这样设计，是因为先手在做出选择之后，就成了后手，后手在对方做完选择后，就变成了先手。这种角色转换使得我们可以重用之前的结果，典型的动态规划标志。
读到这里的朋友应该能理解算法解决博弈问题的套路了。学习算法，一定要注重算法的模板框架，而不是一些看起来牛逼的思路，也不要奢求上来就写一个最优的解法。不要舍不得多用空间，不要过早尝试优化，不要惧怕多维数组。dp数组就是存储信息避免重复计算的，随便用，直到咱满意为止。
了解了动态规划的套路，也不会写状态转移方程，没有思路，怎么办？本文就借助「最长递增子序列」来讲一种设计动态规划的通用技巧：数学归纳思想。
先看一下题目，很容易理解：
注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的。下面先来一步一步设计动态规划算法解决这个问题。
动态规划解法动态规划的核心设计思想是数学归纳法。
相信大家对数学归纳法都不陌生，高中就学过，而且思路很简单。比如我们想证明一个数学结论，那么我们先假设这个结论在k 类似的，我们设计动态规划算法，不是需要一个dp数组吗？我们可以假设dp[0…i-1]dp[0…i1]都已经被算出来了，然后问自己：怎么通过这些结果算出dp[i]？ 直接拿最长递增子序列这个问题举例你就明白了。不过，首先要定义清楚dp数组的含义，即dp[i]的值到底代表着什么？ 我们的定义是这样的：dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。 举两个例子： 算法演进的过程是这样的，： 根据这个定义，我们的最终结果（子序列的最大长度）应该是dp数组中的最大值。 intres=0;for(inti=0;i读者也许会问，刚才这个过程中每个dp[i]的结果是我们肉眼看出来的，我们应该怎么设计算法逻辑来正确计算每个dp[i]呢？ 这就是动态规划的重头戏了，要思考如何进行状态转移，这里就可以使用数学归纳的思想： 我们已经知道了dp[0…4]dp[0…4]的所有结果，我们如何通过这些已知结果推出dp[5]dp[5]呢？ 根据刚才我们对dp数组的定义，现在想求dp[5]的值，也就是想求以nums[5]为结尾的最长递增子序列。 nums[5]=3，既然是递增子序列，我们只要找到前面那些结尾比3小的子序列，然后把3接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。 当然，可能形成很多种新的子序列，但是我们只要最长的，把最长子序列的长度作为dp[5]的值即可。 for(intj=0;jnums[j])dp[i]=Math.max(dp[i],dp[j]+1);}这段代码的逻辑就可以算出dp[5]。到这里，这道算法题我们就基本做完了。读者也许会问，我们刚才只是算了dp[5]呀，dp[4],dp[3]这些怎么算呢？ 类似数学归纳法，你已经可以算出dp[5]了，其他的就都可以算出来： for(inti=0;inums[j])dp[i]=Math.max(dp[i],dp[j]+1);}}还有一个细节问题，dp数组应该全部初始化为1，因为子序列最少也要包含自己，所以长度最小为1。下面我们看一下完整代码： 首先明确dp数组所存数据的含义。这步很重要，如果不得当或者不够清晰，会阻碍之后的步骤。 然后根据dp数组的定义，运用数学归纳法的思想，假设dp[0…i-1]dp[0…i1]都已知，想办法求出dp[i]dp[i]，一旦这一步完成，整个题目基本就解决了。 但如果无法完成这一步，很可能就是dp数组的定义不够恰当，需要重新定义dp数组的含义；或者可能是dp数组存储的信息还不够，不足以推出下一步的答案，需要把dp数组扩大成二维数组甚至三维数组。 最后想一想问题的basecase是什么，以此来初始化dp数组,以保证算法正确运行。