下面通过凸多边形剖分的例子来进一步理解带备忘的自顶向下方法（递归实现）在动态规划中的应用。

题目描述：

假设有一个凸多边形，边的个数为N，其顶点按顺时针表述为A[0],A[1],A[2],...,A[N]。假设你将多边形剖分为N-2个三角形，对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是剖分后所有N-2个三角形的值之和。

求多边形的所有三角剖分中，可以得到的最低分。

例如：

可以发现，第一种剖分的得分是3*4*5+3*4*7 = 144

第二种剖分的得分是3*5*7 + 4*5*7 = 245

输出结果是144。

下面开始分析。第五讲提示过，遇到“最……”的文字，可以考虑动态规划算法，进而可以考虑使用递归来具体实现。

本题如何使用递归呢？

直观的想法如下：把多边形分成两部分：

分别对i顺时针到j的A部分以及j顺时针到i的B部分进行递归，然后考虑合并。但合并时，会有一些麻烦，如下所示：

看起来合并A和B时，仍然需要从A和B中分别选择2个点和1个点（或者反过来）进行组合求解，这种情况下解法不清晰。

下面考虑特定的边p[1]p[2],包含该边的所有三角形集合如下：p[1]p[2]p[3],p[1p[2]p[4],p[1]p[2]p[k]。。。，p[1]p[2]p[n]，如下图所示：

对于特定的三角形p[1]p[2]p[k](下图中,k=4)，将多边形分成了如下三部分：

这种情况下分别求出A、B部分的最小得分，加上三角形p[1]p[2]p[k]的得分，即可得到剖分中包含三角形p[1]p[2]p[k]的所有组合中的最小得分。

接着通过循环+递归的形式，对k进行遍历，求出所有包含p[1]p[2]p[k]的三角形剖分中的最小值(其中k=3,4,...n)，也就是题目的所求的最小得分。代码如下：

weight = [1,3,1,4,1,5]import sysdef decompose(weight):    if len(weight)<3:        return 0    min_value = sys.maxsize           #maxsize适用于python3    for i in range(2,len(weight)):        partA = weight[1:i+1]        partB = [weight[0]]        partB.extend(weight[i:])        min_value = min(min_value, weight[0]*weight[1]*weight[i]+decompose(partA)+decompose(partB))    return min_value print(decompose(weight))

本代码中对应的测试用例和最优解如下：

程序的预期输出是1*5*1+1*4+1+1*3+1+1*1*1 = 13

下面分析代码，partA完成A部分的构造，即构建多边形p[1]p[2]p[3]...p[i]；

partB完成B部分的构造，即构建多边形p[i]p[i+1]...p[n]p[1]

weight[0]*weight[1]*weight[i]+decompose(partA)+decompose(partB)) 完成三部分的得分相加。

运行程序，可以输出最小得分为13，符合预期。

分析上述代码，大家会发现代码不优雅的同时，会额外申请大量空间，究其原因，在于我们B部分的点是由p[i]p[i+1]p[n]p[1]组成的，其序号不连续，导致我们无法简单的递归调用来实现B部分的求解，只能通过额外构造数组来表示该多边形，再递归求解。

如何解决B部分下标不连续的问题呢？将基准边选定为p[n]p[1]即可，如下图所示：

B部分变成由p[i]p[i+1]...p[n]组成。

代码修改为：

weight = [1,3,1,4,1,5]import sys def decompose(weight,i,j):    if j-i<2:        return 0    min_value = sys.maxsize    for k in range(i+1,j):        min_value = min(min_value, weight[i]*weight[j]*weight[k]+decompose(weight,i,k)+decompose(weight,k,j))    return min_value print(decompose(weight,0,len(weight)-1))

本代码没有进行备忘，会存在大量的重复调用，为此，加上缓存：

import sysweight = [1,3,1,4,1,5]cache = {}hits = 0def decompose(weight,i,j):    global hits    if (i,j) in cache:        hits += 1        return cache[(i,j)]    if j-i<2:        return 0    min_value = sys.maxsize    for k in range(i+1,j):        cache[(i,k)] = decompose(weight,i,k)        cache[(k,j)] = decompose(weight,k,j)        min_value = min(min_value, weight[i]*weight[j]*weight[k]+cache[(i,k)]+cache[(k,j)])    return min_value print(decompose(weight,0,len(weight)-1))print(hits) 

程序输出正确结果13，同时输出缓存命中次数26，证明缓存确实起了作用。

注意的是，本题目没有严格证明对于p[1]p[2]p[k]（k=3，4，。。。n)进行递归调用后，就完整覆盖了所有的三角剖分情形，这一点大家可以探讨下。

小结一下，编写代码时，需要对代码质量进行评估，如果发现代码实现比较笨拙或者代码不够优雅，需要进一步重构思路和代码。

后续我们将从递归形式转化到自底向上构建的形式来求解动态规划问题。