如何将此递归函数转换为动态算法？

Question

我目前正在处理这个问题：

某种字符串处理语言提供了一种原始操作，将字符串分为两部分。由于此操作涉及复制原始字符串，因此无论切割的位置如何，长度为n的字符串需要n个单位。现在，假设您想将一根弦分解为许多碎片。休息的顺序会影响总运行时间。例如，如果您想在位置3和10上切一个20个字符的字符串，那么在位置3下切下的第一个切割将产生20+17 = 37 10 = 30。给出一种动态编程算法，鉴于M剪切的位置在长度为n的字符串中，发现将字符串分解为M + 1件的最低成本。

我设法将问题表示为复发，并提出了以下问题的递归解决方案。

def recursive(M, N):
if len(M) == 0:
    return 0
else:
    c_min = float('inf')
    for c in M:
        lt_cuts = [d for d in M if d < c]
        gt_cuts = [e - c for e in M if e > c]
        c_min = min(c_min, N + recursive(lt_cuts, c) + recursive(gt_cuts, N - c))

return c_min

通常，一旦我发现问题的递归形式，将其调整为动态算法就很容易。这次，我一整天都在面对这个问题，找不到单个工作解决方案。谁能给我一些提示或有用的片段？任何事情都将不胜感激。

Answer 1

让我们的切口从1到m，我们将其称为字符串“切割0”的开始，并将字符串的末端“切割M+1”。

现在，对您的递归函数的每个调用都计算成本（i，j），这是切割cut i 和剪切的最低成本代码> j ，带有i＆lt; j。

在计算成本（i，j）的计算中，您只会对较小区域进行递归调用。如果您调用成本（a，b），则您将拥有（ba）＆lt; （JI）。

因此，您可以通过创建一个矩阵成本来实现动态编程实现，其中 cop> cop [i] [j] = cop（i，j）。如果您按增加区域长度（JI）的顺序填充矩阵，则可以确保您需要计算任何费用[i] [j] 的所有条目，将在您的时间之前完成需要他们。

例如，给定所有剪切位置（包括开始和结束） cuts ：

# costs for all length-1 regions
for i in range(len(cuts)):
    COST[i][i+1] = 0

# costs for other sizes
for size in range(2,len(cuts)+1):
    for i in range(len(cuts)-size+1):
        j = i+size

        # cost for this region if we start by cutting at i+1
        subcost = COST[i][i+1] + COST[i+1,j]

        # costs for other initial cuts
        for cut in range(i+2,j):
            subcost = min(subcost, COST[i][cut] + COST[cut,j])

        # add the cost of the initial cut
        COST[i][j] = subcost + cuts[j] - cuts[i]