算法设计与分析 课件 第六章 动态规划

动态规划第六章主讲人：邱维阳E-mail:qwynick@163.com动态规划的思想核心概念：状态记录：合理记录、表示问题状态转移：将子问题的解合并为原问题的解前提条件：最优子结构：原问题的最优解可由某个（些）子问题的最优解转移而来无后效性：将子问题的解转移到原问题时，不用关心子问题最优解的起源重叠子问题：反复利用子问题的解，减少计算量上述概念比较抽象，可以结合各种例题进行体会和理解。线性动态规划6.2线性动态规划——动态规划入门线性动态规划主要特征：状态可以表示为某种序列：比如一维线性序列或者二维、三维阵列数据表示。状态的转移表现为：由某个位置的数据（状态）按照某种固定的顺序计算另一个位置的数据（状态）。线性动态规划例6-1：升国旗的平台一共需要上N级台阶，你每一步可以上一级或者两级，问一共有多少种登上平台的走法？可尝试枚举n=1、2、3……时的走法，并找一下规律。很容易发现当n=1、2、3、4、5……时的走法有1、2、3、5、8种。即斐波那契数列。但是这是为什么呢？线性动态规划分析：假定你已经走到了第n级台阶，很显然你的前一步只可能站在第n-2或者n-1级台阶。也就是，如果你能走到n-2或者n-1级台阶，那么你都可以通过再走一步到达第n级台阶。所以如果你走到第n-2级台阶有x种方式，走到第n-1级台阶有y种方式，则走到第n级台阶就有x+y种方式。我们记走到第i级台阶的方案数为dp[i]（状态记录），则可以得到下面的关系：dp[i]=dp[i-2]+dp[i-1]这个递推关系正好与斐波那契数列一致。线性动态规划例6-1小结：作为引子，本例非常简单，但是却已经蕴含了动态规划的思想，从1走到n的问题的解，由1走到n-2的解和1走到n-1的解合并而成，且走得近的问题构成了重叠子问题。复杂度为𝑂(𝑛)。线性动态规划例6-2：给你一个长度为𝑛的整数序列𝑑，请你找出一段连续子序列，使得该段子序列的和最大。比如𝑑=[6,−1,5,4,−7]，则最大的子序列为6-1+5+4=14。直接暴力枚举区间起点和终点，复杂度将是𝑂(𝑛2)。线性动态规划分析：观察一下，有时候我们需要包含负数以获得后面更大的正数序列（如示例）；但有时候，又不需要包含负数，比如𝑑=[6,−10,5,−7]。那么如何找到一个统一的做法呢？或者说是否会包含负数的判定依据是什么呢？线性动态规划分析：仔细对比𝑑=[6,−1,5,4,−7]和𝑑=[6,−10,5,−7]，可以发现，对于前者，6-1=5，即是说包含负数之后总和依然为正，会对后面的区间形成正的贡献；而后者则不然。所以我们可以得出一个规律，如果包含负数之后仍然为正，就继续向后延伸（有正贡献），反之则不要延伸（由负贡献）。如果我们用dp[i]表示到i位置为止的最大子段和，则可以得出下面的转移方程：dp[i]=max(dp[i-1],0)+d[i]线性动态规划例6-2小结：只需要将𝑑数组循环一遍即可得到以每个数作为区间右端点的最大区间和，复杂度为𝑂(𝑛)。这是一个非常经典的动态规划入门题，但是仍然值得用来品味动态规划的前提条件。在本例中，以i为区间右端点的最大区间和由以i-1为区间右端点的最优区间加上i自己和或者由i自己单独作为一个区间两者中更优的一个转移而来。这里很好地体现了最优子结构和无后效性，请同学们注意体会。线性动态规划例6-3：第i个木桩的高度为hi，运动员一开始在编号为1的木桩上，每次可以跳到所在木桩后面第1个或第2个木桩上。当运动员从第i个木桩跳到第j个木桩时，他将消耗体力|hi-hj|。试问，跳到第n个木桩，最少需要消耗多少体力？直接暴力枚举所有的跳跃方案，复杂度将是O(2n)。线性动态规划分析：思考：如果我们到达终点n所耗费的体力是dp[n]，那么，这个dp[n]是怎么来的？按照题目的限制，只能是由n-2或者n-1位置跳过来。所以？线性动态规划分析：如果由n-2跳过来，则：dp[n]=dp[n-2]+|hn-hn-2|同理，如果由n-1位置跳过来，则：dp[n]=dp[n-1]+|hn-hn-1|很显然，我们会选择一个总体力开销更小的方案，即dp[n]=min(dp[n-2]+|hn-hn-2|,dp[n-1]+|hn-hn-1|)线性动态规划分析：我们分析了对于终点的转移策略，很显然，这样的转移策略对前面的各个位置也都适用。同时，要使到达终点的开销尽量小，必然希望到达前面各个点的开销（子问题）也尽量小。所以这满足最优子结构的条件。因此我们可以从前往后逐步计算出到达各个位置的最小开销。dp[i]=min(dp[i-2],dp[i-1])线性动态规划例6-3小结：很显然，只需要将𝑑数组循环一遍即可得到以每个数作为区间右端点的最大区间和，复杂度为𝑂(𝑛)。在本例中，跳到i位置的最小开销一定由其前面两个位置之一转移而来，同时，要使得跳到i的开销尽量小，也要让跳到i-2和i-1的开销尽量小，即从最优子结构转移而来。此外，在考虑跳到第i个点的开销时，单纯考虑了跳到i-2和i-1级的总开销以及从他们跳到第i级这一步的开销，并未关注之前是如何跳到i-2和i-1的，此即无后效性。重叠子问题怎么体现？线性动态规划例6-4：暑假共有n天，每天可以选择学习一门课，在第i天时如果学习三门课A、B、C可获得的知识量分别为ai、bi、ci，为了避免厌倦，憨憨不会在连续两天学习同一门专业课。整个假期憨憨能获得的最大知识量是多少？直接暴力枚举所有的学习方案，复杂度将是O(2n)。线性动态规划分析：参照例6-3的分析，这个问题应该如何分析？很显然，如果如果第i天选择了A课程，则第i+1天可选择的课程为BC，如果第i天选择的是B课程，则第i+1天可选择的课程为AC……同时，类比前一个例题，可以发现如果我们在第i天选择某门课程X，后续的课程选择并不受第i天之前选择的影响。所以？线性动态规划分析：由于第i天的选择会对后续的转移产生不同的影响，我们需要分别记录在第i天的不同选择情况下的最优解：即可以用dpa[i]、dpb[i]、dpc[i]分别表示在第i天选择A、B、C课程的最大收益。根据题目要求，我们在第i天选择A课程的前提是前一天选择了B或者C，即：dpa[i]=max(dpb[i-1],dpc[i-1])+a[i]学习B、C课程的转移方程也可类似得出。不断向后计算，直到第n天即可得到全局最优解。线性动态规划例6-4小结：很显然，只需要将天数遍历一遍即可得到每一天学习A、B、C课程的最优解，复杂度为𝑂(𝑛)。最优子结构如何体现？无后效性如何体现？。重叠子问题如何体现？线性动态规划例6-5：数字三角形的第i行有i个数字，分别表示各处的文物价值，考古人员由第一行那个唯一数字的位置进入陵墓，并可以向下一行中与当前数字位置最接近的两个数字之一的位置前进。求能收集的文物的最大价值。直接暴力枚举所有的行进方案，复杂度将是O(2n-1)。线性动态规划分析：参照例6-3、6-4的分析，这个问题应该如何分析？很显然，从示例里面可以看到，贪心=7+6+2+7+6=28，不成立。隐约仍然有无后效性、最优子结构等性质？所以？线性动态规划分析：由于除边界位置外，其余位置只可能由其上一行的两个位置转移而来，为了使总和更大，很显然，应当选择由更大的一个转移而来，如果我们用dp[i][j]表示走到第i行第j列的总和的最大值，用d[i][j]表示第i行第j列的文物价值，则有：dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+d[i][j]线性动态规划例6-5小结：很显然，只需要从上到下将各行遍历一遍即可得到最优解，复杂度为𝑂(𝑛2)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？线性动态规划例6-6：给定一个数列，请将其中若干个数字移走，使得剩下的数字呈现递增的关系。剩余数字构成的递增序列的长度最长可以为多少？直接暴力枚举所有的移除方案，复杂度将是O(2n)。线性动态规划分析：本问题又该如何分析？如果我们从最后一位的数字4开始向前搜索，第一个能与4构成上升序列的是第5位的1，再往前就没了；第二个能与4构成上升序列关系的是第3位的2，然后是第2位的2，他们又同时能与第1位的1构成上升序列关系。1

2

2519944122111搜索过程分析：本问题又该如何分析？同理，我们考察倒数第二位的数字9，他会找到5，5又会找到2，2又会找到1……。之后，倒数第三位的9又会重复此计算过程……线性动态规划1

2

2

5

19949122111搜索过程52211线性动态规划分析：但是观察搜索过程可以发现，对于黄色和蓝色的2来说，无论是4与他们连接还是5与他们连接，或者是9与他们连接，再往前都只能再连一个1。同样，两个9连接上5之后，再往前能连接的情况也都是一样的。因为再往前能连接的数仅被5所限（无后效性），即继续往前能组成的长度是固定的，因而我们其实没有必要采用搜索来穷举所有方案。4122111912211152211线性动态规划分析：通过前面的分析，我们发现，以第i个数字为终点的上升子序列长度是由d[i]的数值大小与他前面的序列所确定的，且对于i’>i，如有d[i’]>d[i]，则第i’个数就能接上以第i个数作为终点的上升子序列，构成一个更长的上升子序列。如果我们用dp[i]表示以第i个数字为终点的最长上升子序列长度，则有：dp[i]=max(dp[j])+1(满足1≤j<i，且d[j]<d[i])线性动态规划例6-6小结：很显然，一共需要求n个数的最长上升子序列，求第i个最长上升子序列时需要遍历其前面i-1个数，复杂度为𝑂(𝑛2)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？还有复杂度更低的做法吗？线性动态规划例6-7：给定两个数列长度分别为n和m，请将其中若干个数字移走，使得两个数列剩余的部分一致。剩余数列的最长长度是多少？直接暴力枚举所有的移除方案，复杂度将是O(2n+m)。线性动态规划分析：类比例6-6，本问题又该如何分析？我们定义完整的问题为，从第一个串的n个字符中删除部分，从第二个串的m个字符中删除部分，让剩余部分相同，且尽量长。按照之前的经验，我们可以将子问题（状态）描述为：从第一个串的前i个字符中删除部分，从第二个串的前j个字符中删除部分，让剩余部分相同，且尽量长。我们记该问题的最优解为dp[i][j]。分析：状态如何转移？很显然，如果第一个串的第i位与第二个串的第j位相等，我们直接保留两者，即：dp[i][j]=dp[i-1][j-1]+1如果两者不等，又该如何？我们可以考虑舍弃一个，具体舍弃哪个呢？显然是舍弃后，剩余部分匹配长度尽量长的一个方案，即：dp[i][j]=max(dp[i-1][j],dp[i][j-1])线性动态规划线性动态规划例6-7小结：很显然，我们只需要将两个串逐位进行比较即可。复杂度为𝑂(nm)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？线性动态规划总结注意体会、学会如何表示状态、如何转移状态。注意以下特征：无后效性、最优子结构、重叠子问题。多练习多思考多体会。背包问题6.3背包问题——一类非常经典的动态规划问题背包问题例6-9：0-1背包。有n个物品，第i个物品的价值为vi，重量wi。给定一个载重量为m的背包用于装物品。在不超过背包载重量的前提下，如何选择物品使得背包中物品的总价值最大？所有参数不超过1000。直接暴力枚举所有的移除方案，复杂度将是O(2n)。背包问题分析：优先拿单位重量价值高的？考虑m=5，w1=2,

w2=4，v1=5,

v2=8。此时显然物品1的单位价值更大，但是我们却应该拿物品2。分析：如果我们直接枚举所有的物品要或者不要，那么复杂度又是指数级的。联想我们在前一节也遇到了大量的指数级问题，通过动态规划降为了多项式级的复杂度。其原理即利用最优子结构和重叠子问题的性质，避免了大量无效的状态枚举。那么本问题？背包问题背包问题分析：有的物品本身是不够优秀的，或者他与其他物品的组合的结果不够优秀，所以我们在进行价值计算的时候不需要在这些不优的组合的基础上进行进一步计算。对于每个重量，我们只需要在该重量的最大价值方案基础上进一步计算即可。背包问题分析：我们可以用dp[i][j]表示在考察过前i个物品后，重量为j的方案的最大价值。当我们考察第i个物品时，对于每个重量j，我们计算出对应的dp[i][j]值即可：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])这里，max中的第一项表示我们舍弃第i号物品，用前i–1个物品组成重量为j的组合；第二项表示我们使用第i号物品，此时我们只能用前i–1号物品组成重量为j–w[i]的组合，总价值在此基础上需要加上第i号物品的价值。背包问题分析：我们可以用dp[i][j]表示在考察过前i个物品后，重量为j的方案的最大价值。右图是背包载重量为5，三个产品的重量分别为3、2、4，价值分别为2、5、8的运行效果。可以看到在考虑过第1个物品后，载重量为3、4、5可获得价值2；在考虑过物品2后，重量为2、3、4时可以获得价值5，重量为5时可获得价值7。三轮完成后，载重量为5时，可以获得的价值为8。背包问题分析：在实际操作中，对于01背包问题一般并不会用n×m的数组保存数据。从上面的示意图可以看出，当i=2的时候，i=1的数据其实已经无用了；当i=3的时候，i=1的数据已经没用了。我们可以采用滚动数组的形式节省空间。当然，更直接的方法是在一维数组上进行原地修改。（后面介绍）背包问题例6-9小结：每个物品都需要将所有的m个不同重量都更新一遍，一共n个物品，复杂度O(nm)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？背包问题例6-10：完全背包。有n类物品，第n类物品每个价值vi，重量wi，每类物品的个数不限。给定一个载重量为m的背包，求问如何选择物品，在不超过背包载重量的前提下，使得背包中物品的总价值最大。（本题所有输入参数不超过1000）与例6-9有什么区别？背包问题分析：在01背包问题中，每个物品只能用一次，因此dp[i][j]是由dp[i-1][j-w[i]]+v[i]转移而来。在本例中，每个物品都可以无限使用，所以dp[i][j]不仅可以由dp[i-1][j-w[j]]转移而来，还可以由dp[i][j-w[j]]转移而来，即可以由已经使用过第i号物品的组合方案再继续加入i号物品，即：dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-w[i]],dp[i][j-w[i]])+v[i])背包问题分析：dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-w[i]],dp[i][j-w[i]])+v[i])这里第一个max的第一项表示不放入第i号物品；第二个max的第一项表示用了一个第i号物品形成重量j；第二个max的第二项表示再已经用过物品i的基础上继续使用物品i，即由本轮的dp[i]继续进行转移。背包问题分析：我们可以用dp[i][j]表示在考察过前i个物品后，重量为j的方案的最大价值。右图是背包载重量为5，三个产品的重量分别为3、2、3，价值分别为5、4、8的运行效果。0000001234500055500458900488120i=0i=1i=2i=3背包问题例6-10小结：每个物品都需要将所有的m个不同重量都更新一遍，一共n个物品，复杂度O(nm)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？背包问题01背包和完全背包小结：01背包和完全背包作为经典的背包问题，状态较为简单，在实际操作过程中，往往仅采用一维数组进行计算。即，用dp[j]记录重量为j时的最大价值，在解决01背包问题时，我们可以将j从m更新到w[i]，这样先更新大的重量，再更新小的重量，可以避免同一个物品被多次使用。相应地，再解决完全背包问题时，我们可以将j从w[i]更新到m，这样先更新小的重量，再更新大的重量，可以让同一个物品被多次使用。背包问题例6-11：多重背包问题。有n类物品，单个第i类物品的价值为wi，重量vi，每类物品的个数为ci。给定一个载重量为m的背包。求问如何选择物品，在不超过背包载重量的前提下，使得背包总价值最大（本题所有输入参数不超过100）。比如，背包载重量为10，有两种物品重量分别为1和3，价值分别为1和2，数量分别为8和2，经过分析和试算可以得出应该取走7个第一类物品和1个第二类物品。总计取得价值为9。更复杂了？背包问题分析：对于多重背包问题，最简单的处理方式就是将ci个第i号物品处理成ci个独立的重量为wi，价值为vi的物品即可。总体来看，就是∑ci个物品组成的01背包问题。背包问题例6-11小结：每个物品都需要将所有的m个不同重量都更新一遍，一共∑ci个物品，复杂度O(nmc)。但是此问题其实通过更高级的处理技术，可以将复杂度降低到O(nmlogc)，甚至O(nm)。有兴趣的同学可以自行查阅资料。背包问题例6-12：二维背包。有n个物品，第i个物品的体积为si，价值为vi，重量wi。给定一个容积为m、载重量为r的背包。求问如何选择物品，在不超过背包容积和载重量的前提下，使得背包总价值最大。（本题所有输入参数不超过100）更复杂了？背包问题分析：相对于之前的问题，本问题将约束条件扩展到了两个，如何求解？应该可以想到，我们只需要记录在体积为j，重量为k时的最大价值即可。可以用dp[j][k]来表示前述状态，如果加入物品i后达到该状态，则加入该物品前的状态即为：dp[j-s[i]][k-w[i]]背包问题分析：参照0-1背包的转移方式，在考察第i号物品时，需要同时考虑体积和重量的影响：dp[j][k]=max(dp[j][k],dp[j-s[i]][k-w[i]]+v[i])这里max的第一项表示不加入第i号物品，即最大价值保持不变；而第二项表示加入第i号物品，此时其余物品的总体积为j-s[i]，总重量为k-w[i]，对应的价值即为dp[j-s[i]][k-w[i]]。背包问题例6-12小结：每个物品都需要将所有的m个不同容积和r个不同重量的价值都更新一遍，一共n个物品，复杂度O(nmr)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？背包问题总结背包模型：非常重要的模型，多种衍生问题。注意不同背包问题的状态记录。注意不同背包问题的状态转移顺序。背包问题有非常多的衍生内容，打好基础非常重要。记忆化搜索与区间动态规划6.4记忆化搜索与区间动态规划

——换一个方向进行动态规划记忆化搜索与区间动态规划例6-14：已知斐波那契数列f(1)=f(2)=1，其他f(x)=f(x-2)+f(x-1)，输入正整数n，输出f(n)，n不超过46。

这个题目很简单，直接for循环递推求解即可。记忆化搜索与区间动态规划分析：同学们应该也知道，也可以采用递归的方式计算斐波那契数列即，要求解f(n)如果n<=2：返回1；否则：返回前两项之和f(n-2)+f(n-1)。这样做有什么问题？记忆化搜索与区间动态规划分析我们可以画出递归求解的递归树。从右侧的树中可以观察到两个特点，①所有的递归终点都是n=1或者n=2，其值为1。由于斐波那契数列的结果：指数级上升由特征①：递归的结点数指数级上升。速度极慢。f(5)f(3)f(4)f(1)f(2)f(2)f(3)f(1)f(2)f(4)f(2)f(3)f(1)f(2)f(6)记忆化搜索与区间动态规划分析②同一个数字，无论出现在何处，其子树的形态都一致。由特征②：同样数值的节点没必要反复计算。可以在首次计算完成后——记录结果——后续直接调用。dp[i]=dp[i-2]+dp[i-1]以上dp数组的数值仅在第一次访问i节点时进行计算。递归终点：n=1、2。f(5)f(3)f(4)f(1)f(2)f(2)f(3)f(1)f(2)f(4)f(2)f(3)f(1)f(2)f(6)记忆化搜索与区间动态规划例6-14小结：由于原问题可能多次拆分出同样的子问题，而子问题的结果是确定的，因此只需要在第一次拆分出该子问题时进行计算并保存结果。复杂度O(n)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？记忆化搜索与区间动态规划例6-15：给定一个n×m的矩形滑雪场，已知各处的海拔，滑雪者只能由高处滑向低处，请求出一个最长的滑雪路径。某滑雪场的海拔分布如图所示。

在这样一个海拔分布的滑雪场，可以选择从中间的25出发，逆时针转圈滑行，滑出一个长度为25的路径。记忆化搜索与区间动态规划分析：很显然，暴力搜索是不可能很快求解的。根据动态规划思想，如果我们已经确定了某个位置(x,y)的最长滑行长度L，则与其相邻的位置(x,y+1)如果能够滑到(x,y)，则可以继续滑行L长度。但是这意味着：要得到(x,y+1)的结果，必须先知道(x,y)的结果。（循环反复）。由于分支很多，事先确定并计算位置(x,y+1)对应的各个的(x,y)形成悖论。（实际上也可以通过对高度排序后逐位置计算，但比较麻烦）记忆化搜索与区间动态规划分析类比我们在前一例中的处理思路。由于对每个位置，他的最长滑行长度是唯一确定的，我们只要计算一次即可。如果用dp[x][y]记录滑行长度，则有dp[x][y]=max(dp[x’][y’])+1（(x,y)与(x’,y’)相邻且前者比后者高）之后如果有相邻点再次滑到(x,y)，直接取用之前保存的结果即可。递归终点：该位置无法继续滑行。f(5)f(3)f(4)f(1)f(2)f(2)f(3)f(1)f(2)f(4)f(2)f(3)f(1)f(2)f(6)记忆化搜索与区间动态规划例6-15小结：每个位置的最优滑行长度仅由周围四个位置的高度和滑行长度所决定，因此需要访问周围四个点共四次（每个位置亦最多被递归进入四次），一共n×m个位置，所以复杂度O(nm)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？记忆化搜索与区间动态规划例6-16：有排成一排的n堆石子，从左往右第i堆有di个石子。将相邻两堆石子进行合并的代价为两堆石子的石子个数之和。请设计一个方案将所有堆合并为一堆石子且代价最少（𝑛不超过500）。比如初始有4堆石子，分别为d=[4,4,2,5]，此时可以先合并左边两个再合并右边两个得到d=[8,7]，再整体合并得到d=[15]，总代价为8+7+15=30。

记忆化搜索与区间动态规划分析：很显然，从样例数据可以看出，直接贪心地优先合并最小的是错的。请自行验证。记忆化搜索与区间动态规划分析：由于石子是两两合并，所以在最终合并完成前，一定是两堆。我们可以穷举最后一步合并前，这两堆的原始分界线，即：d1=[4]，d2=[4,2,5]d1=[4,4]，d2=[2,5]d1=[4,4,2]，d2=[5]记忆化搜索与区间动态规划分析：总合并代价为分别将左侧和右侧合并为一堆的代价，以及最后将两堆合并成一堆的代价。很显然，在本题定义的合并代价下，后者是固定值，而前者需要在所有的划分方案中选择代价最小的一个。这样，我们每递归一层，问题都会变小，直到最终求解。记忆化搜索与区间动态规划分析：我们以将原数组切分为d1=[4]，d2=[4,2,5]为例：d2又可以切分为d21=[4],d22=[2,5]以及d21=[4,2],d22=[5]两种，代价分别7+11=18和6+11=17。既然两种方式都是合并成d2这一堆，代价尽量小比较优。42542542525711426117+11=186+11=17记忆化搜索与区间动态规划分析：求出d2=[4,2,5]的最小合并代价17后，继续将d1=[4]，d2=[4,2,5]进行合并，可得全部石子合并代价为17+15=32。同理可以得到d1=[4,4]，d2=[2,5]的最小代价为8+7+15=30。同理可以得到d1=[4,4,2]，d2=[5]的最小代价为16+15=31。则在各种切分d1、d2的方案中，选择最优的一个，总代价为30。42544254425417+15=3215+15=3016+15=31记忆化搜索与区间动态规划分析：那么，如何记录状态呢？这题与前面的题目都不太一样了，需要表述的是一段范围，我们可以用dp[l][r]表示将l~r合并成一段所需的最小代价。这个区间的代价只在第一次被询问到时需要计算，之后就可以直接调用了。要求解dp[l][r]，只需要枚举所有的分断位置，找出左右子区间的合并代价和最小的方案即可，即：dp[l][r]=min(dp[l][x],dp[x+1][r])+sum(l~r)(l≤x<r)这里sum(l~r)表示最后一次将l~r合并成一堆石子的代价。递归终点：l==r。记忆化搜索与区间动态规划例6-16小结：区间总共有约n2/2个，每个区间可能的分断点为O(n)级别，所以复杂度O(n3)。最优子结构如何体现？无后效性如何体现？重叠子问题如何体现？记忆化搜索与区间动态规划例6-17：有n堆石子排成一个圆圈，从顺时针数第i堆有ai个石子。每次操作，将相邻两堆石子进行合并的代价为两堆石子的石子个数之和。请设计一个方案将所有相邻堆合并为一堆石子且代价最小（n不超过250）。合并次数是多少？记忆化搜索与区间动态规划分析：很显然合并次数是n-1，因此一定有一个相邻关系未用于合并，直接枚举这个位置（将其分断成串），可以得到正确的结果。但是复杂度是多少？记忆化搜索与区间动态规划分析：可以发现，这样的切断，存在大量的重复计算，比如总长度为100，对比将100/1之间切断的方案，与将1/2之间切断的方案，从2~100范围内的所有区间其实都是一样的，没有必要重新求。1234989910012349899100597……记忆化搜索与区间动态规划分析：如何能够更好地利用这些数据呢。这涉及一个常用的处理环形的技巧，将环形切断成串后，然后复制一份并拼接在原串后面。此时可以发现，这样一个长