464. 我能赢嗎 : 博弈論 DP 運用題

題目描述

這是 LeetCode 上的 ​​464. 我能赢嗎 ，難度為 中等。

Tag : 「博弈論 DP」、「記憶化搜尋」、「狀态壓縮」

在 "100 game" 這個遊戲中，兩名玩家輪流選擇從 到 的任意整數，累計整數和，先使得累計整數和 達到或超過  的玩家，即為勝者。

如果我們将遊戲規則改為 “玩家 不能 重複使用整數” 呢？

例如，兩個玩家可以輪流從公共整數池中抽取從 到 的整數（不放回），直到累計整數和 >= 。

給定兩個整數 ​

​maxChoosableInteger​

​​ （整數池中可選擇的最大數）和 ​

​desiredTotal​

​​（累計和），若先出手的玩家是否能穩赢則傳回 ​

​true​

​​ ，否則傳回 ​

​false​

​ 。假設兩位玩家遊戲時都表現 最佳 。

示例 1：

輸入：maxChoosableInteger = 10, desiredTotal = 11

輸出：false

解釋：
無論第一個玩家選擇哪個整數，他都會失敗。
第一個玩家可以選擇從 1 到 10 的整數。
如果第一個玩家選擇 1，那麼第二個玩家隻能選擇從 2 到 10 的整數。
第二個玩家可以通過選擇整數 10（那麼累積和為 11 >= desiredTotal），進而取得勝利.
同樣地，第一個玩家選擇任意其他整數，第二個玩家都會赢。
      

示例 2:

輸入：maxChoosableInteger = 10, desiredTotal = 0

輸出：true
      

示例 3:

輸入：maxChoosableInteger = 10, desiredTotal = 1

輸出：true
      

提示:

二維博弈論 DP（TLE）

這是一道博弈論 DP 的題，為了友善，我們使用 來表示 ，使用 來表示 。

由于 資料範圍為 ，且每個數隻能選一次，我們可以使用一個二進制數 來表示 範圍内的被選擇的數的情況：二進制表示中 的位置代表數已被選擇，否則代表尚未選擇。

首先樸素二維狀态表示相對容易想到：定義 為目前已被選擇的數為 ，輪數為 時，「原始回合的先手」能否獲勝（ 代表能， 代表不能），其中 從 開始，通過 的奇偶性可知是原始回合的先手還是後手。

設計遞歸函數來實作「記憶化搜尋」，函數 ​

​int dfs(int state, int tot, int k)​

​​ 表示目前狀态為 ， 對應累計和， 代表輪數，最終答案通過判斷 ​​

​dfs(0, 0, 0)​

​​ 是否為 來得知。

轉移過程中，如果發現目前回合的決策，能夠直接使得累積和超過 ，說明目前回合玩家獲勝；或者如果目前決策能夠導緻下一回合的玩家失敗的話，目前回合玩家也獲勝，否則目前玩家失敗。

代碼：

class Solution {
    int n, t;
    int[][] f = new int[1 << 20][2];
    // 1 true / -1 false
    int dfs(int state, int tot, int k) {
        if (state == ((1 << n) - 1) && tot < t) return -1;
        if (f[state][k % 2] != 0) return f[state][k % 2];
        int hope = k % 2 == 0 ? 1 : -1;
        for (int i = 0; i < n; i++) {
            if (((state >> i) & 1) == 1) continue;
            if (tot + i + 1 >= t) return f[state][k % 2] = hope;
            if (dfs(state | (1 << i), tot + i + 1, k + 1) == hope) return f[state][k % 2] = hope;
        }
        return f[state][k % 2] = -hope;
    }
    public boolean canIWin(int _n, int _t) {
        n = _n; t = _t;
        if (t == 0) return true;
        return dfs(0, 0, 0) == 1;
    }
}      

• 時間複雜度：共有個狀态，每個狀态轉移需要複雜度，整體複雜度為
• 空間複雜度：

優化狀态表示

進一步發現，若能優化輪數次元，可以有效減少一半的計算量，我們調整狀态定義為：定義 為目前狀态為 ，「目前先手」能否獲勝（ 代表能， 代表不能）。

同時調整遞歸函數為 ，最終答案通過判斷 ​​

​dfs(0, 0)​

​​ 是否為 來得知。

注意這裡調整的重點在于：将記錄「原始回合的先後手發起 和 原始回合的先後手獲勝情況」調整為「目前回合發起 和 目前回合獲勝情況」。

代碼：

class Solution {
    int n, t;
    int[] f = new int[1 << 20];
    // 1 true / -1 false
    int dfs(int state, int tot) {
        if (f[state] != 0) return f[state];
        for (int i = 0; i < n; i++) {
            if (((state >> i) & 1) == 1) continue;
            if (tot + i + 1 >= t) return f[state] = 1;
            if (dfs(state | (1 << i), tot + i + 1) == -1) return f[state] = 1;
        }
        return f[state] = -1;
    }
    public boolean canIWin(int _n, int _t) {
        n = _n; t = _t;
        if (n * (n + 1) / 2 < t) return false;
        if (t == 0) return true;
        return dfs(0, 0) == 1;
    }
}      

• 時間複雜度：共有個狀态，每個狀态轉移需要複雜度，整體複雜度為
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.464​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。