【スナップアルゴリズム】877-石子ゲーム

タイトル
アレックスと李はいくつかの石でゲームをしています.偶数の石が1列に並んでいて、それぞれの石には正の整数の石pilesがある[i].
ゲームは誰の手の中の石が一番多いかで勝負を決める.石の総数は奇数なので引き分けはありません.
アレックスと李は交代で行い、アレックスは先に始めた.ラウンドごとに、プレイヤーは行の開始または終了から石の山全体を取り出します.このような状況は、より多くの石の山がないまで続き、この時、手にした石が最も多いプレイヤーが勝った.
アレックスと李が最高のレベルを発揮したと仮定し、アレックスが試合に勝ったときにtrueに戻り、李が試合に勝ったときfalseに戻る.
例:

  ：[5,3,4,5]
  ：true
  ：
       ，     5     5     。
       5  ，        [3,4,5] 。
       3  ，       [4,5]，        5     10  。
       5  ，       [3,4]，        4     9  。
   ，   5                   ，       true 。

ヒント:

2 <= piles.length <= 500

piles.lengthは偶数です.

1 <= piles[i] <= 500

sum(piles)は奇数です.

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/stone-game著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題解
方法一:動的計画
構想
ゲームのルールを変えて、李が得点するたびにアレックスの点数から差し引かれるようにしましょう.
dp(i,j)をアレックスが得ることができる最大点数とし,残りの堆積中の石数はpiles[i],piles[i+1],...,piles[j]である.
これはスコアゲームでは自然です.ゲームの各位置の値を知りたいです.
dp(i+1,j)とdp(i,j−1)に基づいてdp(i,j)の再帰を策定することができ,この再帰中の作業を繰り返さないように動的プログラミングを用いることができる.この方法は,状態がDAG(有向無ループ図)を形成するため,正しい答えを出力することができる.
アルゴリズム#アルゴリズム#
残りの山の石の数がpiles[i],piles[i+1],...,piles[j]の場合,順番に回ったプレイヤーには最大2つの行為がある.
j-iとN modulo 2を比較することで、順番の人を見つけることができます.
プレイヤーがアレックスであれば、piles[i]またはpiles[j]の石を取り出し、点数を増やす.
その後、合計はpiles[i]+dp(i+1,j)またはpiles[j]+dp(i,j-1)に分けられる.私たちはその中の最大の可能性のある得点がほしいです.
プレイヤーが李であれば、piles[i]またはpiles[j]の石を取り出し、アレックスの数の点数を減らす.
その後、合計は-piles[i]+dp(i+1,j)または-piles[j]+dp(i,j-1)に分けられる.私たちはその中の最小可能性の得点がほしいです.

class Solution {
    public boolean stoneGame(int[] piles) {
        int N = piles.length;

        // dp[i+1][j+1] = the value of the game [piles[i], ..., piles[j]].
        int[][] dp = new int[N+2][N+2];
        for (int size = 1; size <= N; ++size)
            for (int i = 0; i + size <= N; ++i) {
                int j = i + size - 1;
                int parity = (j + i + N) % 2;  // j - i - N; but +x = -x (mod 2)
                if (parity == 1)
                    dp[i+1][j+1] = Math.max(piles[i] + dp[i+2][j+1], piles[j] + dp[i+1][j]);
                else
                    dp[i+1][j+1] = Math.min(-piles[i] + dp[i+2][j+1], -piles[j] + dp[i+1][j]);
            }

        return dp[1][N] > 0;
    }
}

複雑度分析
時間複雑度:O(N^2)で、Nは石の山の数である.空間複雑度:O(N^2)であり,この空間は各サブゲームの中間結果を格納するために用いられる.
方法2:数学
構想とアルゴリズム
明らかに、アレックスはいつも2つのゲームを勝ち取った.いくつかの努力を通じて、私たちは彼女がいつも4つのゲームを勝ち取ったことを知ることができます.
もしアレックスが最初に最初の山を手に入れたら、彼女はいつも3番目の山を取ることができます.もし彼女が最初に4番目の山を取ったら、彼女はいつも2番目の山を取ることができます.第1+第3、第2+第4の少なくとも1組はもっと大きいので、彼女はいつも勝つことができます.
この考えをNスタックの場合に拡張することができる.第一、第三、第五、第七杭を白色とし、第二、第四、第六、第八杭を黒色とする.アレックスはいつもすべての白い杭やすべての黒い杭を手に入れることができ、そのうちの1つの色が持つ石の数は必ず別の色より大きい.
そのため、アレックスはいつも試合に勝つことができる.

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

複雑度分析
時間と空間の複雑さ:O(1).
作者:LeetCodeリンク:https://leetcode-cn.com/problems/two-sum/solution/shi-zi-you-xi-by-leetcode/出典:力扣(LeetCode)著作権は作者の所有.商业転載は作者に连络して授権を得て、非商业転載は出典を明記してください.
感想
数学の方法return trueは本当に騒々しい操作です......