python之动态规划没有给出正确答案

我最近发现了一种叫做动态规划的技术，我偶然发现了一个我无法弄清楚的问题。一开始你会得到一个参数列表，你需要像切割它一样进行求和。如果列表只有一个元素，则不对它求和。如果它有更多，则将元素相加并以各种可能的方式进行切割。所以如果 list 有 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 ] ) ) 

感谢您的宝贵时间和任何答复!

请您参考如下方法:

我想这就是你想要的:

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() 很好。您忘记做的是写下每个节点与其子节点之间的关系。如果您这样做了，我几乎可以肯定您自己会找到正确的解决方案。

我们还没有完成(感谢 Stefan Pochmann 注意到)。为了构建真正的动态规划解决方案，您还需要避免多次解决同一问题。目前，运行 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)。