将这个递归解法转化为动态规划

Question

给定一个整数栈，玩家轮流从栈顶移除1、2或3个数字。假设对手采取最佳策略，并且您先选择，我想到了以下递归方法：

int score(int n) {
    if (n <= 0) return 0;

    if (n <= 3) {
        return sum(v[0..n-1]);
    }

    // maximize over picking 1, 2, or 3 + value after opponent picks optimally
    return max(v[n-1] + min(score(n-2), score(n-3), score(n-4)),
               v[n-1] + v[n-2] + min(score(n-3), score(n-4), score(n-5)),
               v[n-1] + v[n-2] + v[n-3] + min(score(n-4), score(n-5), score(n-6)));
}

基本上，每个级别都会比较选择1、2或3后，你的对手选择1、2或3所得出的结果。

我在思考如何将其转换为DP解决方案，因为它显然是指数级的。我很困惑的是似乎有三个维度：你的选择数量、对手的选择数量和子问题大小，即似乎需要维护table[p][o][n]的最佳解决方案，其中p是你选择的值的数量，o是你的对手选择的数量，n是子问题的大小。

我真的需要这三个维度吗？我看到了一个类似的问题：http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/，但无法适应它。

- alh

---

你能给一个简单的例子来解释一下这个游戏吗？ - Vikram Bhat

@VikramBhat（栈顶）-->12 1 7 10 2 9 3。您可以将12、12+1或12+1+7添加到您的分数中。这些数字从堆栈中取出，然后您的对手轮流从剩余的堆栈中选择1、2或3个数字。您会继续轮流进行，直到没有数字为止。 - alh

那么计数最多的那个赢了，对吧？ - Vikram Bhat

我在想如何将这个问题转化为动态规划的解法，因为它明显是指数级别的。最简单的方法是使用记忆化技术。 - Karoly Horvath

@KarolyHorvath 备忘录技术在技术上并不等同于动态规划。动态规划是自底向上的，而备忘录技术则是自顶向下的，并且还使用堆栈。你可以通过动态规划节省大量空间。例如，通过仅存储最后三个子解来使用DP，可以在O（1）的额外空间内解决此问题。 - Vikram Bhat

Answer 1

以下是将问题转化为DP的方法：

score[i] = maximum{ sum[i] - score[i+1] , sum[i] - score[i+2] , sum[i] - score[i+3]  } 

这里的score[i]表示从游戏 i 到 n 中生成的最大分数，其中v[i]是堆栈顶部。 sum[i]是从 i 到末尾所有元素的总和。可以使用一个单独的DP在O（N）时间复杂度内评估sum[i]。以上DP问题可以在O(N)的时间复杂度内使用表格解决。

以下是JAVA中的DP解决方案：

public class game {

    static boolean play_game(int[] stack) {
        if(stack.length<=3)
            return true;
        int[] score = new int[stack.length];
        int n = stack.length;
        score[n-1] = stack[n-1];
        score[n-2] = score[n-1]+stack[n-2];
        score[n-3] = score[n-2]+stack[n-3];
        int sum = score[n-3]; 
        for(int i=n-4;i>=0;i--) {
            sum = stack[i]+sum;
            int min = Math.min(Math.min(score[i+1],score[i+2]),score[i+3]);
            score[i] = sum-min;
        }
        if(sum-score[0]<score[0]) 
            return true;

        return false;
    }

    public static void main(String args[]) {
        int[] stack = {12,1,7,99,3};
        System.out.printf("I win => "+play_game(stack));
    }

编辑：

为了获得DP解决方案，您需要以较小的实例形式将问题的解决方案视觉化。例如，在这种情况下，由于两个玩家都在最佳状态下玩游戏，在第一次选择后，第二个玩家还会为其剩余堆栈获得最佳分数，这是第一个玩家的子问题。唯一的问题在于如何在递归中表示它。要解决DP问题，您必须首先定义与任何计算方式中当前问题之前的子问题相关的递归关系。现在我们知道无论第二个玩家赢得多少，第一个玩家都会输，因此第一个玩家实际上获得第二个玩家的总和 - 分数。由于第二个玩家也是最佳状态下玩游戏，因此我们可以用递归的方式表达解决方案。

- Vikram Bhat

---

我能看到这个代码是如何工作的，但我想知道你是怎么得出它的；有没有特定的方法？将它组合在一起的直觉性解释是什么？ - alh

@alh 基本上你需要找到一个基于较小问题的递归关系，这些问题可以独立地进行评估。请查看我的编辑。 - Vikram Bhat