本文转载自微信公众号《神奇的程序员》，作者是神奇的程序员。转载本文请联系神奇程序员公众号。前言动态规划是一种比较难懂的算法思想。本文以自己的理解，通俗易懂的方式讲解动态规划。欢迎有兴趣的开发者阅读本文。思路分析接下来我们通过一个例子一步步分析，引出动态规划的思路。假设，你家里有无数张三种面额（1元、5元、11元）的纸币，现在你需要用这些纸币凑够一定的金额。我们如何匹配他们用最少的钞票得到这个金额？例如：我们需要凑15元钱。贪念——只在我们眼前根据我们的生活经验，我们必须先用面纸较大的钞票，再减去总金额。思路是这样的：先拿一张11元的钞票，接下来要补的是4元（15-11）要补4元，只能用1元的钞票来补，需要4张1元纸币（4-1-1-1-1）15元凑，我们一共用了5张纸币（11元一张，1元4张）。我们称这种策略为贪心。我们设要收的金额为w，要使用的纸币面额为m。贪心策略会让w尽快变小。每减少一次，我们就会面临正确的情况是补上w-m。经过我们的大脑计算，这个策略不需要最少的纸币来凑15元。我们可以直接用三张5元纸币来凑这个数额。更好的解决方案——动态规划我们在用贪心思维解决这个问题的时候，只考虑眼前的情况，格局很小，那么现在应该如何避免这种情况呢？如果我们用暴力枚举来凑数额，显然时间复杂度太高了，太多的组合可以凑齐这个数额，枚举起来的时间是受不了的。重叠子问题接下来，让我们试着找出这个问题的本质。一开始如果我们拿一张面值为11的钞票，那么我们接下来面临的问题就是在金额为4的情况下补足最少需要的钞票数量。value为5，那么我们面临的下一个问题就是当金额为10时，最少需要补多少张纸币。一开始，如果我们取一张面额为1的纸币，那么我们面临的下一个问题是当金额为14时，最少需要补几张纸币。经过上面的分析，我们会发现这些问题有一个共同的形式：给定一个金额，最少需要补多少张纸币。我们将一个大问题分解为三个子问题。接下来，我们再分析一下这三个子问题。我们用f(n)表示凑n最少需要的钞票数量，用cost表示凑w需要的钞票数量。那么：如果我们取11，那么最后使用的纸币总量是：cost=f(4)+1如果我们取5，那么最后使用的纸币总量是：cost=f(10)+1如果取1，最后使用的纸币数量为纸币总数为：cost=f(14)+1观察上面的问题后，我们会发现一个共同点：每次取一张面额的纸币，我们需要计算剩余金额最少需要多少张纸币，它们的计算方法都是一样的。所有三个子问题都需要以相同的方式解决，因此它们是重叠的子问题。最优子结构当我们要凑15块钱的时候，我们需要的钞票总数是上面三种情况下需要钞票数量最少的一张。我们在求f(n)的时候，需要计算出金额为n时最少需要多少张纸币，比如f(10)，我们只能用2种面额的纸币（5元和1元）。如果我们用5元来凑的话，我们需要的钞票数量是：f(5)+1。如果我们用1元来凑的话，我们需要的钞票数量是：f(9)+1、当我们在寻找f(n)时，其子问题的解肯定会找到需要最少硬币数的那个，即：f(n)=min(f(n-1),f(n-5),f(n-11))+1一个大问题的最优解可以从一个子问题的最优解推导出来，这个性质称为最优子结构。无后效通过上面的分析，我们知道当数量为15时，我们需要求出3个重叠的子问题的解，最优的就是最终问题的解。这三个子问题有它们自己重叠的子问题。当我们解决这些重叠的子问题时，我们只需要知道最终的答案即可，而不用关心它们是如何计算的，因为它们的计算过程不会影响后面的问题。影响。比如：f(4)、f(10)、f(14)，我们只需要找出它们的具体值即可，它们的计算过程对我们后面要解决的问题没有影响。如果某一阶段的状态给定，则该阶段以后的过程发展不受该阶段前一阶段状态的影响，称为无后效，即未来与过去无关.割绳子有一根长度为n的绳子，将绳子切成m段（m和n都是整数，n>1且m>1），每根绳子的长度记为k[0]，k[1],...,k[m]。k[m]*k[1]*...*k[m]的最大可能乘积是多少？例如：绳子的长度是8，我们把它分成三段，此时得到的最大乘积是18。思路分析下面我们来分析一下这个例子，看看能不能用动态规划求解。根据题意，我们可以知道以下信息：绳子的长度必须大于1且每次至少剪一次我们用f(n)表示一根绳子所有剪法的最大乘积长度为n那么，当绳子的长度为2时，我们只有一种切割方式，从中间开始切割，这条绳子会被切割成两小段，每段长度为1，如下图所示：n=2，f(n)=1*1=1，即：f(2)=1我们继续分析n=3的情况，如下图，它有2种切割方式切割成两个长度为1和长度为2的小段，分别剪成长度1、1、1三个小段从剪法2可以看出，其实就是对长度为2的绳子进行剪裁。经过前面的分析一下，我们已经知道它的所有切割方式的最大乘积是1，那么它们的乘积就是1*1*1=1。所以，我们不除，直接取切割方式1的乘积，即：f(3)=2再来看n=4的情况，如下图，它有3种切割方式，长度为1切割两个小的将长度为3的绳子分成两个长度为2的小绳子和两个长度为2的小绳子，再切成四个长度为1的小绳子。从切割方法1可以看出，长度为3的绳子的最大乘积为计算(f(3)=2)，如果我们把这部分绳子剪掉，乘积会变小，所以我们选择不剪掉这部分绳子，那么剪法1的最大乘积是1*3=3、从切割方法2可以看出，两根绳子的长度为2，我们计算出绳子长度为2的最大乘积(f(2)=1)。如果被切割，乘积变小，那么切割方法2的最大乘积就是2*2=4。综上所述，我们可以发现这样一个规律：无论绳子最终被切割成多少块，都必须被一刀斩断。那么，对于一根绳子，一旦被剪断一次，就会分为2个子问题：如何剪断切割点左侧的绳索，如何剪断切割点右侧的绳索，因为我们从1开始往回推，前面的绳子怎么剪，我们已经保存了。分析到这里，我们发现已经满足了动态规划的两个特点：重叠子问题：绳子被剪断后，绳子的每一部分都可能继续分裂，需要面对的子问题每次都是相同的最优子结构：在分割绳子的每一部分时，我们需要找出这部分绳子的所有切割方法的最大乘积，满足最优子结构的特征。我们来分析一下n=5的情况，如下图，我们的第一次切割有两种切割方式：分别从位置1和从位置2，可以将绳子切割成长度为1和长度为4的两小段，length2和length3的两个短段，我们用一个数组（result）来存放前面得到的绳子的最大乘积（最优解）。综上所述，我们知道当绳子的长度小于4时，每根绳子的长度最大乘积是固定的，即：result[0]=0result[1]=1result[2]=2result[3]=3注：因为绳子至少要被切割一次，并且绳子的长度大于1，所以当绳子的长度为1时，不能被切割，所以它的最大乘积为1。当绳子的长度是2或3，我们不拆分它，所以它们的最大乘积是它自己的长度。观察上图我们发现，当绳子的长度大于等于4时，第一次切割的位置最多只能切割到绳子长度的一半。我们已经计算出每一种切割方式的子问题并放入结果中，我们只需要将每一种切割方式的子问题的最优解相乘就可以得到最大值。当n=4时，第一刀能切的位置可以是：1、2：result[4]=max(result[1]*result[3],result[2]*result[2])=max(1*3,2*2)=max(3,4)=4当n=5时，第一刀能切的位置可以是：1、2：result[5]=max(result[1]*result[4],result[2]*result[3])=max(1*4,2*3)=max(4,6)=6当n=6时，第一刀可切的位置可以是：1,2,3result[6]=max(result[1]*result[5],result[2]*result[4],result[3]*result[3])=max(1*6,2*4,3*3)=max(6,8,9)=9研究到这里，我们会发现，在求子问题的最优解时，我们只关心它的结果，而不会关心它的计算过程影响到我们最终问题的解，那么它也满足动态规划的最后一个性质：无后效的递归公式经过上面的一系列推导，我们发现这个问题满足了动态规划的三个性质，那么就是了说这个问题可以用动态规划来解决。经过上面的分析，我们知道绳子无论怎么剪都会被剪成两部分，然后分别求解两部分的最大乘积，那么当绳子的长度为n时，就可以得到如下公式：result[n]=result[i]*result[n-i]n为当前所需绳索长度，i为当前切割位置。无论绳子从哪里剪断，都会被剪成两截。我们求这两段的乘积，每一种切割方式的最大乘积就是一根长度为n的绳子的最大乘积。实现代码经过上面的一系列分析，我们已经彻底掌握了解决这个问题的方法。有了思路，我们就可以用代码来实现了，如下图（TypeScript代码）：publiccutTheRope(length:number):number{//因为绳子只能按整数切割，当绳子的长度小于2时,不能剪if(length<2){return0;}//当绳子长度为2时，只能从中间剪，所有剪法的最大乘积1if(length===2){return1;}//当绳子的长度为3时，可以切割成//1.111//2.12//1*2>1*1*1，所以当长度为3时，所有的最大乘积切割方式为2if(length===3){return2;}//创建结果数组，存放每段绳子切割长度的最大乘积constproducts=newArray
