Блог

Учитывая стопку целых чисел, игроки по очереди удаляют 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, поскольку оно явно экспоненциально. Я боролся с тем фактом, что, похоже, у него есть 3 измерения: число вашего выбора, число выбора оппонента и размер подзадачи, т. Е. Кажется, Что лучшее решение для table[p][o][n] необходимо поддерживать, где p количество выбранных вами значений, o это число вашего оппонентавыбирает и n определяет размер подзадачи.

Мне действительно нужны 3 измерения? Я видел эту аналогичную проблему: http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game / , но, похоже, не смог его адаптировать.

Вот способ, которым проблема может быть преобразована в 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] может быть оценен с использованием отдельного DP в O (N) . Вышеупомянутый DP может быть решен с помощью таблицы в O (N)

Редактировать : — Ниже приведено решение DP на JAVA :-

 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 у второго игрока. Поскольку второй игрок также играет оптимально, мы можем выразить решение в терминах рекурсии.