如果我们解决一个问题的时候能将一个大问题转换成一个或者若干个规模较小的同等性质的问题，当我们求解出这些小问题的答案后，大问题的答案很容易解决,对于这样的情况，显然我们可以递归（或者说分治）的方式解决问题。如果在求解这些小问题的过程中发现有些小问题我们需要重复计算多次，那么我们就干脆把已经求解过的小问题的答案记录下来放在一张表中，这样下次遇到这个小问题，我们只需要查表就可以直接得到结果，这个就是动态规划的白话讲解。动态规划的难点在于如何定义问题及子问题。
1）如果可以将一个规模较大的问题转换成一个或若干个规模较小的子问题，也就是能找到递推关系，这个时候我们不妨先将程序写成递归的形式。
2）如果使用递归求解规模较小的问题上存在子问题重复求解的现象，那么我们就建立一张表（有可能这个表只有一行）记录需要重复求解的子问题。填表的过程和将大问题划分为子问题的方式相反，我们会从最简单的子问题开始填表。现在我们就利用这个套路解决下面这些经典的问题。
问题描述：菲波那契数列的定义f(n)=f(n-1)+f(n-2)，且f(1)=1,f(2)=1，求f(n)的值。斐波那契数列的定义本身就是将大问题转换成两个同性质的子问题，所以我们可以直接根据定义写成递归形式。
publicstaticintrecursion(intn){if(n<0){return0;}if(n==1||n==2){return1;}returnrecursion(n-1)+recursion(n-2);}我们以f(6)为例现在把递归的过程画出来
我们发现在求解F(6)时，需要求解F(2)四次，求解F(1)三次，求解F(3)三次，F(4)两次，所以说我们的算法的效率是很低的。提高效率的办法就是将F(1)，F(2)，F(3)….的结果放在表中，下次要计算这些问题的时候我们直接从表中获取就好了，这就是一个最简单的动态规划的例子。现在我们按照套路，从最小的子问开始填表就好了。
publicstaticintdynamic(intn){int[]table=newint[n+1];table[1]=1;table[2]=1;/*从小到大填表*/for(inti=3;i 问题描述：总共有n个楼梯，每次可以走2个台阶，或者每次走3个台阶，或者每次走5个台阶，请问这n个楼梯总共有几种走法。 n个阶梯的问题，可以分解成三个小问题，即n-2个阶梯有几种走法，n-3个阶梯有几种走法，n-5个阶梯有几种走法，而n个阶梯的走法就是这三种走法的和。或者可以反过来思考，你已经站在最后一个台阶上了，那么到达最后一个台阶的情况只能是三种情况，最后一步恰好走2个台阶恰好到达，最后一步恰好走3个台阶恰好到达，最后一步恰好走5个台阶恰好到达。通过这个思想，我们就可以写出递归形式的代码。 publicstaticintrecursion(intn){if(n<0){return0;}if(n==0){return1;}returnrecursion(n-5)+recursion(n-3)+recursion(n-2);}显然上面递归的处理方式需要重复计算很多子问题，画出递归调用的图就一目了然，由于该图和上一个问题的图很类似，这里就省略了。因此就创建一张表，把子问题的结果都记录下来，dp[i]表示走到第i个阶梯有多少种走法。按照套路，我们应该从小的阶梯数开始填表。 publicstaticintdynamic(intn){int[]record=newint[n+1];record[0]=1;for(inti=0;i 问题描述：从顶部出发在每一个节点可以选择向下或者向右下走，一直走到底层，要求找出一条路径，使得路径上的数字之和最大。 对于上图所示的数塔：最大值为379,绿色的的数字就是被选择的节点。 这个问题不能使用贪心算法，请大家自己用三层的阶梯列举出反例。我们现在试着将这个问题分解成子问题，如下图所示。想求得最大值，我们只要选择的红色边框数塔最大值和蓝色边框数塔的最大值中更大的那个，然后加上32，就整个数塔的最大值。这样我们就将一个大的问题转化成了两个规小的问题，然后这两个规模较小的问题还可以继续分解成更小的子问题。根据这个思路，我们可以得到如下递归形式的代码。 上图中的紫色边框数塔既存在于红色边框数塔中，也存在于蓝色边框数塔中，会重复计算两次。实际上，我们使用递归时重复计算的问题显然不止这一个，所以效率不高。为此我们应该创建一张和数塔形状一样的三角形表用来记录更小的数塔的最大值。我们table表示这个表，表中table[i][j]位置的值表示以（i，j）为顶点的数塔的最大值。我们用a[i][j]表示数塔中第i行，第j列的值。那么table[i][j]=a[i][j]+Math.max(table[i-1][j],table[i-1][j-1])。按照套路，我们应该从最小的数塔开始填表。按照table[i][j]的定义，table表的最下面一行就应该等于数塔表中的最下面一行。 按照定义，我们就可以填倒数第二行的dp[i][j]。 table[4][0]=79+Math.max(0,71)=150table[4][1]=69+Math.max(71,51)=140table[4][2]=78+Math.max(51,82)=160table[4][3]=29+Math.max(82,91)=120table[4][4]=63+Math.max(91,64)=154填入到table表的倒数第二行，如下图所示 有了倒数第二行，我们就可以推出倒数第三行，依次类推，我们就可以得到最上面table[0][0]的数值，它就表示了整个数塔的最大值。除了最大值，如果我们还需要知道走了哪些路径，我们还应该定义一个path表，在填table[i][j]时，同时填写path[i][j]。path[i][j]表示了以（i,j）为顶点的数塔的最大值是由两个子数塔（table[i-1][j]为顶点的数塔和table[i-1][j+1]为顶点的数塔）中的哪一个得到的。 最大值：379路径为：行:0,列：0行:1,列：0行:2,列：1行:3,列：2行:4,列：2行:5,列：33.4零-壹背包问题问题描述：有n个物品，它们有各自的重量（weight）和价值（value），现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和此时背包中的物品？一个物品只有不拿和拿两种情况，可以用0和1表示，所以称之为0-1背包问题。 我们来看一个具体的例子。假设有如下物品： 求背包容量在10的时候的能装物品的最大价值，以及装了哪些物品 我们可能首先想到的是贪心算法，我们算出每种物品的单位重量价值（weight/value）,然后按照单位重量价值排序。我们放入物品时首先选择单位重量价值高的物品,直到放不下为止。但是很遗憾，这样得不到最优解。我们不妨列举一个极端的例子，假设只有两个物品，A的value=2.9，weight=2.1；B的value=3，weight=3，显然物品A的单位重量价值要大于B的单位重量价值，但对于容量为3的背包，我们应该选择物品B，所以贪心算法失效。对于0-1背包问题，贪心选择之所以不能得到最优解是因为：它无法保证最终能将背包装满，而部分闲置的背包空间使每公斤背包空间的价值降低了。 回到上面具体的这个问题，它可以表述为 maxValue{宝石、剃须刀、ipad、充电宝、iphone|背包容量10}， 每个物品只有选和不选两种结果，我们不妨从第一个物品开始。如果选了宝石，那么问题转化为当前背包已有价值为50，并在剩下的背包容量（10-4）的前提下，再剩下的物品中（即剃须刀、ipad、充电宝、iphone）选取出最大的价值；如果不选宝石，那么问题转化为当前背包价值为0，并在剩下的背包容量10的前提下，在剩下的物品中（即剃须刀、ipad、充电宝、iphone）选取出最大的价值。我们只需要选择： 50+maxValue{剃须刀、ipad、充电宝、iphone|背包容量6} 与 0+maxValue{剃须刀、ipad、充电宝、iphone|背包容量10} 中较大的那个。而这就直接转化成两个子问题的求解，显然我们已经可以用分治的方式解决这个问题了。我们不妨把递归树（或者说分治树）画出来。 上图就是0-1背包问题的递归树，图左文字边表示当前可选的物品，节点中的值表示背包的容量。我们没有把整个递归树全部都画出来，因为图中我们就已经发现了需要重复计算的子问题。如果背包容量变大，物品种类变多，那么需要重复计算的子问题就越多。需要说明的是上图中有三个背包容量为7的子问题，但是只有被标记的两个子问题才是重复的子问题，因为这两个子问题的背包容量一样，可选物品一样。为了避免子问题的重复求解，我们就建立一张动态规划表，下次遇到重复的子问题，我们就直接查表。下图表示了动态规划表和递归树之间的关系。 那我们现在的主要问题就变成了如何填这样一张表。我们用一个名为dp的二维数组表示这张表，dp[0]行需要单独初始化，从dp[1]行开始填表，规则：从左到右，从上到下。 dp[i][j]表示前i个物品（包括物品i），在背包容量为j时能装的最大价值。 dp[i][j]为下面两者的最大值： 1）物品i不放入背包中：背包容量为j时，前i-1个物品组合出的最大价值 2）物品i放入背包中：物品i的价值+除去物品i占用的重量后，剩余背包容量j-weight(i)由前i-1个物品组合出的最大价值 用公式表示为 1）如果dp[i][j]>dp[i-1][j]，说明该物品i被放入到了背包中，令i=i–1,j=j–weight[i]，然后重复步骤1。 2）如果dp[i][j]==dp[i-1][j]，且只想得到背包最大价值的其中一种的物品一种组合方式，不妨认为该物品i没有被放入到了背包中，令i=i–1,重复步骤1）。 对于步骤2），如果 dp[i][j]==dp[i-1][j]&&dp[i][j–weight(i)]+value(i)==dp[i][j] 说明物品i可以放入背包中（令i=i–1,j=j–weight[i]），也可以不用放入背包中（令i=i-1）。这里就产生分支,说明放入背包中的物品组合方式不唯一，为了简单起见，我们找到一种物品的组合方式即可。 160[4,3,2,0]如果我们仅仅需要知道最大的价值，不需要知道装了哪些物品，我们就可以对空间复杂度进行优化，动态规划表只需要一维，因为dp[i][]仅和dp[i-1][]有关。 Givenanon-emptyarraycontainingonlypositiveintegers,findifthearraycanbepartitionedintotwosubsetssuchthatthesumofelementsinbothsubsetsisequal. Note: 1.Eachofthearrayelementwillnotexceed100. 2.Thearraysizewillnotexceed200. Example1: Input:[1,5,11,5] Output:true Explanation:Thearraycanbepartitionedas[1,5,5]and[11]. Example2: Input:[1,2,3,5] Output:false Explanation:Thearraycannotbepartitionedintoequalsumsubsets. 这是LeetCode的原题。这个问题本质上还是0-1背包问题，背包容量是数组之和的一半，物品的价值和体积是1比1的关系，额外条件是需要把背包装满。 问题描述：有n种物品，它们有各自的重量（weight）和价值（value），现有给定容量的背包，每种物品可以拿任意多个，如何让背包里装入的物品具有最大的价值，以及每种物品装了几个？ 假设，我们还是利用0-1背包中的物品,背包容量为11。 完全背包问题也可以转化成0-1背包问题。因为第i个物品最多拿“背包重量/（物品i的重量）”个，也就是说在0-1背包问题中每个物品i占一行，完全背包问题中，每个物品占“背包重量/（物品i的重量）”个行，按照这个思路显然已经能够解决这个问题。现在我们不把这个问题转化为0-1背包问题，而从这个问题的根源直接思考。 完全背包问题可以表述为 maxValue{宝石、剃须刀、ipad、充电宝、iphone|背包容量10} 每个物品只有选和不选两种结果，我们不妨从第一个物品开始。如果选了宝石，那么问题转化为当前背包已有价值为50，并在剩下的背包容量（10-4）的前提下，继续在{宝石、剃须刀、ipad、充电宝、iphone}选取出最大的价值；如果不选宝石，那么我们就在{剃须刀、ipad、充电宝、iphone}中选择一种，那么问题转化为当前背包价值为0，并在剩下的背包容量10的前提下，再剩下的物品中即{剃须刀、ipad、充电宝、iphone}选取出最大的价值。 因此我们只需要选择： 50+maxValue{宝石、剃须刀、ipad、充电宝、iphone|背包容量6} 中较大的那个。 而这就直接转化成两个子问题的求解，显然我们已经可以用分治的方式解决这个问题了。我们同样可以把递归树画出来，同样还会发现存在需要重复求解的子问题，为了避免子问题的重复求解，我们还是建立一张动态规划表，下次遇到重复的子问题，我们就直接查表。这里我们直接给出动态规划表，我们用一个名为dp的二维数组表示这张表，dp[0]行单独初始化，从dp[1]行开始填表，规则：从左到右，从上到下。 dp[i][j]为下面二者的最大值： 同样，从dp表中我们还可以知道哪些物品被选择了，选择多少次。我们还是从右下角开始回溯。 1）dp[i][j]>dp[i-1][j]说明i号物品被选择了，j=j–weight[i] 2）dp[i][j]==dp[i-1][j]为了简单起见，我们认为i号物品没有被选择，令i=i-1（实际上这里同样可能存在分支，即最大价值时物品的组合方式和数量并不唯一，我们这里为了简单处理，就不考虑这个问题了）。 Youaregivencoinsofdifferentdenominations([dnɑ:mnen]面额)andatotalamountofmoneyamount.Writeafunctiontocomputethefewestnumberofcoinsthatyouneedtomakeupthatamount.Ifthatamountofmoneycannotbemadeupbyanycombinationofthecoins,return-1。 Input:coins=[1,2,5],amount=11 Output:3 Explanation:11=5+5+1 Input:coins=[2],amount=3 Output:-1 我们首先看一下子序列的定义。假设给定一个字符串，我们抽取任意多个不超过字符串长度的字符，并保持它们的前后关系，这样的字符我们称之为子序列。对于字符串ABCDEFG而言，BEF、C、AG等等都是它的一个子序列。 Longestcommonsequence问题：给定两个字符串s1和s2，求这两个字符串中最长的公共子序列。比如给定两个字符串s1：bdcaba和s2：abcbdab，它们的公共子序列 长度为4，最长公共子序列是：bcba。 字符串s1的长度用n表示,字符产s2的长度用m表示，字符串s1和s2的最长公共字串用lcs（n，m）。那么这个问题可以转化为三个子问题 1）求lcs(n-1,m-1) 2）求lcs(n-1,m) 3）求lcs(n,m-1) 当我们求的上述三个子问题的答案，那么lcs(n,m)的结果就可以通过如下方式得到： 如果s1[n]==s2[m] lcs(n,m)=lcs(n-1,m-1)+1 如果s1[n]！=s2[m]： lcs(n,m)=max{lcs(n-1,m-1),lcs(n-1,m),lcs(n,m-1)} 但是实际上lcs（n，m）只要转化成两个子问题lcs(n-1,m)和lcs(n,m-1)就好了。 而子问题lcs(n-1,m-1)是没有必要的，因为lcs(n-1,m-1)必定小于等于lcs(n-1,m)和lcs(n,m-1)中的en任意一个。从常理上来说很好理解，不可能两个字符串中的任意一个变长了，公共子序列反而减少了。而本质上是由于lcs(n-1,m-1)也是lcs(n-1,m)和lcs(n,m-1)这两个问题的子问题。 通过上面的分析，我们把大的问题转化成小的问题，就可以通过递归（或者说分治）的方式把问题解决了，下面就是递归对应的代码。 第0行，表示“b”和“bdcaba”的公共子序列，可以单独处理，同理第0列也可以单独处理，填表完成后如上图所示。从第二行开始，dp表按照从上到下，从左到右的填表顺序填表。根据子递归中子问题的定义，dp[i][j]的取值如下： 当填完整张表时，右下角的值就是公共子序列的最大长度。如果我们还需要知道公共子序列是什么，那么我们可以从右下角开始回溯，如果dp[i][j]>dp[i-1][j]且dp[i][j]>dp[i][j-1],说明s1[i]或者s2[j]是公共子序列，否则选择走dp[i-1][j]和dp[i][j-1]中较大的那个,同样第0行要单独处理。 贪心算法：如果为了方便的解决这个问题，我们需要将大问题化简成小问题，在所有小问题中，仅选择对当前最有利的小问题作为我们解决大问题的基础。 动态规划：如果为了方便的解决这个问题，我们需要将大问题化简成小问题，记录已解决过的小问题，将所有小问题中的最优解作为我们解决大问题的基础。换句话说，能用贪心算法解决的，动态规划算法也肯定能解决，反之不成立。 能用动规解决的问题的特点 1)问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。 2)无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。