我最近发现了一种称为动态编程的技术,但偶然发现了一个我无法解决的问题。开始时会给您一个参数列表,您需要进行总结,就像您要削减它一样。如果列表仅包含一个元素,则不对其求和。如果还有更多,则对元素求和并以各种可能的方式进行削减。因此,如果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
)的情况。