动态规划不能给出正确的答案

Question

我最近发现了一种叫做动态规划的技术，我偶然发现了一个我搞不懂的问题。在开始的时候，你会得到一个论点列表，你需要做加法，就好像你在削减它一样。如果列表只有一个元素，就不能求和。如果它有更多的元素，你就把元素加起来，然后用各种可能的方法进行切割。所以，如果列表有n个元素，就只有n-1种方法来剪切它。图片将解释：

我首先想总结一下所有可总结的部分，我预期结果是20（11+9）（甚至认为正确的答案是9），但我认为这将是一个好的开始。但我的代码返回37，我不知道为什么。我做错什么了？你知道吗

summ = 0

def Opt( n ):
    global summ

    if len( n ) == 1:
        return 0
    else:
        summ += sum( n )
        for i in range( 1,len( n ) ):
            summ += Opt( n[ :i ] ) + Opt( n[ i: ] )

        return summ

print( Opt( [ 1,2,3 ] ) )

谢谢你的时间和回答！你知道吗

Answer 1

我想这就是你想要的：

def Opt(n):
    if len(n) == 1:
        return 0
    else:
        return sum(n) + min(Opt(n[:i]) + Opt(n[i:])
                            for i in range(1, len(n)))

示例：

>>> Opt([1])
0
>>> Opt([1, 2])
3
>>> Opt([2, 3])
5
>>> Opt([1, 2, 3])
9
>>> Opt([1, 2, 3, 4])
19

动态规划就是把“大问题”分解成小的子问题。你知道吗

因此，首先，您应该确定大问题与子问题的关系。你可以通过写一个循环关系来实现。在这种情况下：

Opt(nums) = sum(nums) + min(...)

你还需要一个起点：

Opt(nums) = 0 iff len(nums) == 1

如您所见，一旦编写了递归关系，将其转换为Python代码通常非常简单。你知道吗

理解每个子问题都是自包含的，不需要外部输入，这一点很重要。使用global变量不仅产生了错误的结果，而且违背了动态规划的精神。你知道吗

使用树来表示Opt()是很好的。您忘记了编写每个节点及其子节点之间的关系。如果你这样做了，我几乎可以肯定你自己会找到正确的解决办法。你知道吗

我们还没有完成（谢谢你的注意）。为了构建真正的动态规划解决方案，还需要避免多次解决同一问题。目前，运行Opt([1,2,3,4])会导致多次调用Opt([1,2])。防止这种情况的一种方法是使用记忆法：

cache = {}

def Opt(n):
    # tuple objects are hashable and can be put in the cache.
    n = tuple(n)

    if n in cache:
        return cache[n]

    if len(n) == 1:
        result = 0
    else:
        result = sum(n) + min(Opt(n[:i]) + Opt(n[i:])
                              for i in range(1, len(n)))

    cache[n] = result
    return result

顺便说一下，记住处理n为空的情况（即len(n) == 0）。你知道吗