两人硬币游戏：在动态编程中追踪最佳序列

Question

[两名玩家轮流选择外部硬币之一。最后，假设两名球员发挥最佳，我们将计算其得分之间的差异。例如列表{4,3,2,1}，最佳顺序为4、3、2、1。那么我将获得4 + 2 = 6分，而对手则为4分。现在，我开发了一种算法，如下所示：

我的工作是打印分数，以及索引的最佳顺序。因此在数组{4,3,2,1}中，最佳序列将为0,1,2,3。

最大运行时和内存不应超过n ^ 2。因此，我使用自下而上的方法实现了上述算法，并且可以打印分数，但是我不知道如何在运行时跟踪最佳序列。

我试图创建Pairs或多维ArrayList来记录序列及其相应的备忘[i] [j]，最后打印出具有最大备忘值的那一行……嗯，它们起作用了，但是内存然后所需的值将大于n ^ 2，这在我的任务中是不允许的。

因此，是否有一个不需要那么多存储空间的更好的主意？

任何帮助，不胜感激！

Answer 1

我想您的问题与Predict the Winner of LeetCode (486)相似，但您希望进行一些小的更改：

Java

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[][] dp = new int[length][length];

        for (int i = 0; i < length; i++)
            dp[i][i] = nums[i];

        for (int l = 1; l < length; l++)
            for (int i = 0; i < length - l; i++) {
                int j = i + l;
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }

        return dp[0][length - 1] >= 0;
    }
}

Python

class Solution:
    def PredictTheWinner(self, nums):
        length = len(nums)
        memo = [[-1 for _ in range(length)] for _ in range(length)]

        @functools.lru_cache(None)
        def f():
            def helper(nums, i, j):
                if i > j:
                    return 0

                if i == j:
                    return nums[i]

                if memo[i][j] != -1:
                    return memo[i][j]

                cur = max(nums[i] + min(helper(nums, i + 2, j), helper(nums, i + 1, j - 1)),
                          nums[j] + min(helper(nums, i, j - 2), helper(nums, i + 1, j - 1)))

                memo[i][j] = cur
                return cur

            score = helper(nums, 0, length - 1)
            total = sum(nums)
            return 2 * score >= total

        return f()

对于第二个解决方案N，空间复杂度可能是provided in this link的数量级。

参考

Most optimal solutions are here in the discussion board