LeetCode 486は勝者HERODINGのLeetCodeの道を予測する

スコアを表す非負の整数配列を指定します.プレイヤー1は配列の任意の端から1つの点数を取り、その後プレイヤー2は残りの配列の任意の端から点数を取り続け、プレイヤー1が取る.......毎回1人のプレイヤーは1つの点数しか取れず、点数が取られた後は取れません.残りの点数が取れないまでゲームは終わります.最終的に得点合計が最も多かったプレイヤーが優勝した.
スコアを表す配列を与え,プレイヤー1が勝者になるか否かを予測する.各プレイヤーの遊び方が彼の点数を最大化すると仮定することができます.
例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に戻る.
例2:
入力:[1,5,233,7]出力:True解釈:プレイヤー1が最初に1を選択する.そしてプレイヤー2は5と7から選択しなければならない.プレイヤー2がどちらを選択しても、プレイヤー1は233を選択できます.最終的に、プレイヤー1(234点)がプレイヤー2(12点)より多くの点数を獲得したため、Trueに戻り、プレイヤー1が勝者になれることを示した.
ヒント:

1 <=         <= 20.
                  10000000 。
             ，     1     。

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/predict-the-winner著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題を解く構想:これは中程度の難易度の問題で、実現するのは難しくなく、再帰と動態計画で解決することができる.最も肝心なのは転移方程式を構築することで、まずテーマを分析する:1.偶数個の数であれば、Aは必ず勝つことができる.Aが負けたら、Bの取り方でもう一度やってもいいし、配列長が1 Aでも必ず勝つからだが、奇数の場合はダイナミックプランニングアルゴリズムが必要になり、状態遷移方程式は:dp[i][j]=Mathである.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])dp[i][j]は、[i,j]区間において、現在の持つべき数のプレイヤーと後に持つ数のプレイヤーとの点数差の最大値(現在取るべき数のプレイヤーであることに注意し、このプレイヤーは必ずしも最初の先手プレイヤーではない)を示すコードは以下の通りである.

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        if(nums.size() % 2 == 0 || nums.size() == 1){//    ，             ，          
            return true;
        }
        //          
        //dp[i][j]  ： [i,j]   ，                       （           ，                 ）
        int dp[20][20];
        for(int i = 0; i < nums.size(); i ++){
            dp[i][i] = nums[i];
        }
        //      :dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
        //   ，i        ， j        
        for(int i = nums.size() - 2; i >= 0; i --){
            for(int j = i + 1; j < nums.size(); j ++){
                dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][nums.size() - 1] >= 0;
    }
};