两周前，我在这里发布了有关动态编程的THIS问题。用户Andrea Corbellini准确地回答了我想要的内容，但是我想进一步解决该问题。
这是我的职责
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,2,3,4,5 ] )
前面的问题解决了计算最佳值的问题。现在，
而不是为上面的示例计算最佳值33，我想打印出我们获得最佳解的方法（通往最佳解的路径）。因此，我想以列表的形式打印列表被剪切/分割的索引，以获得最佳解决方案。因此，上述示例的答案将是：
[ 3,2,1,4 ]（在第三个标记/索引处剪切极点/列表，然后在第二个索引处剪切，然后在第一个索引之后剪切，最后在第四个索引处剪切）。答案应该是列表形式。列表的第一个元素将是索引，在该索引中，列表的第一次剪切/分割应在最佳路径中进行。第二个元素将是列表的第二个切割/分区，依此类推。
也可以有其他解决方案：
[ 3,4,2,1 ]
他们俩仍然会引导您获得正确的输出。因此，打印哪一张都没有关系。但是，我不知道如何跟踪和打印动态编程解决方案所采用的最佳路径。
顺便说一句，我想出了一个非递归的解决方案，该问题已在上一个问题中解决。但是，我仍然不知道为最佳解决方案打印路径。这是上一个问题的非递归代码，可能有助于解决当前问题。
def Opt(numbers):
prefix = [0]
for i in range(1,len(numbers)+1):
prefix.append(prefix[i-1]+numbers[i-1])
results = [[]]
for i in range(0,len(numbers)):
results[0].append(0)
for i in range(1,len(numbers)):
results.append([])
for j in range(0,len(numbers)):
results[i].append([])
for i in range(2,len(numbers)+1): # for all lenghts (of by 1)
for j in range(0,len(numbers)-i+1): # for all beginning
results[i-1][j] = results[0][j]+results[i-2][j+1]+prefix[j+i]-prefix[j]
for k in range(1,i-1): # for all splits
if results[k][j]+results[i-2-k][j+k+1]+prefix[j+i]-prefix[j] < results[i-1][j]:
results[i-1][j] = results[k][j]+results[i-2-k][j+k+1]+prefix[j+i]-prefix[j]
return results[len(numbers)-1][0]
最佳答案
这是打印所选内容的一种方法：
在上一个问题中，我使用了@Andrea Corbellini提供的备注的递归解决方案。如下所示：
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
现在，我们有了所有元组（包括所选元组）的缓存值。
使用此方法，我们可以打印选定的元组，如下所示：
selectedList = []
def printSelected (n, low):
if len(n) == 1:
# No need to print because it's
# already printed at previous recursion level.
return
minVal = math.Inf
minTupleLeft = ()
minTupleRight = ()
splitI = 0
for i in range(1, len(n)):
tuple1ToI = tuple (n[:i])
tupleiToN = tuple (n[i:])
if (cache[tuple1ToI] + cache[tupleiToN]) < minVal:
minVal = cache[tuple1ToI] + cache[tupleiToN]
minTupleLeft = tuple1ToI
minTupleRight = tupleiToN
splitI = low + i
print minTupleLeft, minTupleRight, minVal
print splitI # OP just wants the split index 'i'.
selectedList.append(splitI) # or add to the list as requested by OP
printSelected (list(minTupleLeft), low)
printSelected (list(minTupleRight), splitI)
您可以如下所示调用上述方法：
printSelected (n, 0)
关于python - 有关动态编程的更多信息，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35492530/