假设我们有一个名为stones 的数组，其中stones[i] 表示从左数第i 个石头的值。两个朋友 Amal 和 Bimal 用这些石头玩回合制游戏，Amal 总是先开始。n 块石头排成一排。每个玩家可以从行中移除最左边的石头或最右边的石头，并获得等于该行中剩余石头值总和的分数。谁将获得更高的分数将获胜。现在，Bimal 发现他将永远输掉这场比赛，因此他决定将比分的差异降到最低。Amal 的目标是最大化得分的差异。所以我们必须找到 Amal 和 Bimal 得分的差异，如果他们都发挥最佳。
所以，如果输入像stones = [6,4,2,5,3]，那么输出就是6，因为Amal可以取3，所以他的分数是6+4+2+5 = 17，Bimal的分数0到目前为止，数组就像[6,4,2,5]，然后Bimal取6所以他的分数4+2+5 = 11，现在数组是[4,2,5]。然后 Amal 移除 4，所以他的分数 17+2+5 = 24，石头阵列 [2,5] Bob 移除 2，所以他的分数 11+5 = 16，当前的石头阵列 [5] 并且 Amal 移除最后一个值为 5 的石头得了0分，所以他最后的分数是24+0=24，所以他们的分数差是24-16=8。
让我们看看以下实现以获得更好的理解 -
def solve(stones): n = len(stones) dp = [0] * n for i in range(n - 1, -1, -1): v = stones[i] run_sum = 0 for j in range(i + 1, n): new_run = run_sum+stones[j] dp[j] = max(new_run - dp[j], run_sum+v - dp[j - 1]) run_sum = new_run return dp[n - 1] stones = [6,4,2,5,3] print(solve(stones))
[6,4,2,5,3]输出结果
8