我有一个列表，其中(随机)包含 5 到 10 个项目。列表中的第一个整数始终为 0，所有其他整数均为随机正数。它可能看起来像这样:
0 10 50 45 80 5 35
该程序的目标是将列表中的项目视为空格，当您移动到下一个项目时添加到总和中。这个人从 0 开始，总是可以向右移动一个空格或跳过一个空格并落在下一个空格上。例如，对于上面的那个，我可以从 0 到 10，或者第一步从 0 到 50。然后我可以从 50 到 45 或从 50 到 80 等等。
我想找出一个递归算法来遍历这些并找到到达总和最低的最后一项的方法。我应该检查所有可能的组合还是有更简单的方法来做到这一点？这与检查每回合两种可能移动的值(value)并选择较低的值(value)有关吗？
最佳答案
是的，有一种更有效的方法。这个问题看起来非常适合 dynamic programming .这个想法是您以相反的方式看待问题:对于每个 P 位置，您可以从前一个位置或从后面两个位置开始。因此，要找到到达位置 P 的最佳路线，您只需要知道到达位置 (P-1) 的最佳路线> 和 (P-2) 然后比较它们。
如果我正确理解总和计算背后的逻辑，这就是你需要的:
def solve(values):
prev1 = 0
prev2 = 0
for p in range(len(values)):
cur = min(prev1, prev2) + values[p]
prev2 = prev1
prev1 = cur
return cur
和
print(solve([0, 10, 50, 45, 80, 5, 35]))
输出
95
关于Python数学游戏算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48773787/