将此递归解决方案转换为DP

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/，但似乎无法适应它。

Answer 1

这里是将问题转化为DP :-的方法

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

这里是score[i] means max score generated from game [i to n]，v[i] is top of stack。sum[i] is sum of all elements on the stack from i onwards。sum[i]可以在O(N)中使用单独的DP进行评估。在O(N)中使用表可以求解上述DP。

编辑:-以下是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，您必须首先用子问题定义一个递归关系，该关系在当前问题之前以任何计算方式进行。现在我们知道，无论第二名玩家赢了，第一名球员都会有效地获得第二名球员的total sum - score。作为第二玩家，我们也可以用递归来表达解决方案。