Python数学游戏算法

Question

我有一个列表，其中有（随机）5到10项。列表中的第一个int总是0，其他所有int都是随机的正数。可能是这样的：

0 10 50 45 80 5 35

该程序的目标是将列表中的项目视为空格，当您移动到下一个项目时，将其添加到总和中。此人从0开始，始终可以向右移动一个空格，也可以跳过一个空格并在下一个空格上着陆。例如，使用上面的一个，我可以从0到10，或者第一步从0到50。我可以从50到45，或者从50到80等等。你知道吗

我想找出一个递归算法来处理这些问题，并找到一种方法来获得最后一项的总和最低。我应该经历每一个可能的组合，还是有一个更简单的方法来做到这一点？它是否与检查每个回合两个可能动作的值以及选择较低的值有关？你知道吗

Answer 1

是的，有一个更有效的方法。这个问题看起来非常适合于dynamic programming。这个想法是你用相反的方式来看待问题：对于每个位置，你可以从前一个位置，或者从后面的两个位置找到它。因此，要找到到达位置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