算法問題1:玩家預測問題(動态規劃求解)

玩家預測問題概述

給定一個表示分數的非負整數數組。玩家 1 從數組任意一端拿取一個分數，随後玩家 2 繼續從剩餘數組任意一端拿取分數，然後玩家 1 拿，…… 。每次一個玩家隻能拿取一個分數，分數被拿取之後不再可取。直到沒有剩餘分數可取時遊戲結束。最終獲得分數總和最多的玩家獲勝。

舉例:

輸入：[1, 5, 2]

輸出：False

解釋：一開始，玩家1可以從1和2中進行選擇。

如果他選擇 2（或者 1 ），那麼玩家 2 可以從 1（或者 2 ）和 5 中進行選擇。如果玩家 2 選擇了 5 ，那麼玩家 1 則隻剩下 1（或者 2 ）可選。

是以，玩家 1 的最終分數為 1 + 2 = 3，而玩家 2 為 5 。

是以，玩家 1 永遠不會成為赢家，傳回 False 。

提示：

1 <= 給定的數組長度 <= 20.

數組裡所有分數都為非負數且不會大于 10000000 。

如果最終兩個玩家的分數相等，那麼玩家 1 仍為赢家

問題分析

分析:

假設目前的非負數組為nums = {2,5,1}

Int n = nums.length;

我們定義一個二維數組int[][] grade = new int[n+1][n +1]

i:表示數組的最左側;j表示最右側

grade表示玩家(1/2)作為先手在目前這個數組中所取得的最大的相對分數差

我們知道當數組隻有一個元素時,顯然此時無論是玩家1還是玩家2選擇任意一端,其他玩家則無分數可選,則此時的最大相對分數差為此時數組元素值:即grade[i][i] = nums[i];

算法問題1:玩家預測問題(動态規劃求解)

接着,我們首先選擇i=0,j=1的數組{2,5}:

若先手選擇2,則另外一個玩家選擇5:最大分數差為2-5=-3;

若先手選擇5,則另外一個玩家選擇2:最大分數差為5-2=3;

故真正的對于玩家1來說先手取得最大分數差為max(-3,3)=3

同理對于i=1;j=2的數組{5,1}:

取得的先手最大分數差為:max(5-1,1-5) = 4

從上面我們可以發現規律:

grade[i][j] = max(nums[i] – grade[i+1][j],nums[j] – grade[i][j-1]);

分析i=0,j=2的情況:

nums[0] – grade[1][2] = 2 – 4 = -2 ;

nums[2] – grade[0][1] = 1 – 3 = -2;

max(-2,-2) =-2 < 0;說明無論怎麼選,玩家1都輸了

算法問題1:玩家預測問題(動态規劃求解)

grade[i][j] = max(nums[i] – grade[i+1][j],nums[j] – grade[i][j-1])的推導過程

因為每個玩家的玩法都會使他的分數最大化。

我們在進行計算grade[i][j]時:

若玩家1選擇了nums[i]的值,則玩家2必然在前面選擇了最大相對分數,即grade[i+1][j],故玩家1的最大相對分數為: nums[i] – grade[i+1][j]

若玩家1選擇了nums[j]的值,則玩家2必然在前面選擇了最大相對分數,即grade[i][j-1]),故玩家1的最大相對分數為:nums[j] – grade[i][j-1]

故此時玩家1的最終選擇的最大相對分數為:

grade[i][j] = max(nums[i] – grade[i+1][j],nums[j] – grade[i][j-1]);

算法問題1:玩家預測問題(動态規劃求解)

java代碼

package com.bingym.temp02;

public class PredictWinner {
    /*
    * 動态規劃解決玩家預測問題:
    * 給定一個表示分數的非負整數數組。
    * 玩家 1 從數組任意一端拿取一個分數，随後玩家 2 繼續從剩餘數組任意一端拿取分數，然後玩家 1 拿，…… 。
    * 每次一個玩家隻能拿取一個分數，分數被拿取之後不再可取。直到沒有剩餘分數可取時遊戲結束。
    * 最終獲得分數總和最多的玩家獲勝。給定一個表示分數的數組，預測玩家1是否會成為赢家。
    * 每個玩家的玩法都會使他的分數最大化。
    * 分析:
    *
    * */
    public static void main(String[] args) {
        int[] nums = {2,5,1};
        PredictWinner3 winner = new PredictWinner3();
        boolean isWinner = winner.PredictTheWinner(nums);
        if (isWinner) {
            System.out.println("玩家1獲勝");
        }else {
            System.out.println("玩家1失敗");
        }
    }

    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length - 1;
        int[][] grade = new int[n + 1][n + 1];
        //首先對grade[i][i](0<= i <= n)的每個值進行指派
        for (int i = 0; i <= n; i++) {
                grade[i][i] = nums[i];
        }
        //填表操作:動态規劃
        //因為我們需要先計算左索引大的,右索引小的的最大相對分數,後獲得左索引小,右索引大的
        //因為後者的最大相對分數是建立在前者的最大相對分數
        for (int j = 1; j <= n; j++) {
            for (int i = j-1; i >=0; i--) {
                grade[i][j] = Math.max(nums[i]- grade[i+1][j],nums[j] - grade[i][j-1]);
            }
        }
        //最後:i=0,j=nums.length - 1,即為玩家1的最大相對分數
        //我們将其與0進行比較:若大于0:說明玩家1可以勝出;若小于0:則說明玩家1失敗
        if (grade[0][n] >= 0) {
            return true;
        }else {
            return false;
        }
    }
}

算法問題1:玩家預測問題(動态規劃求解)