規(guī)劃解石子游戲II：博弈類問題最優(yōu)策略)
1. 問題背景與理解石子游戲II是LeetCode上一道經(jīng)典的動態(tài)規(guī)劃題目編號1140。這道題屬于博弈類動態(tài)規(guī)劃的典型代表考察玩家在面對游戲規(guī)則時的最優(yōu)決策能力。題目描述兩位玩家愛麗絲和鮑勃輪流從石子堆中取石子每次可以取走前X堆1 ≤ X ≤ 2M然后M變?yōu)閙ax(M, X)。游戲的目標是獲得最多的石子。這類博弈問題在實際中有諸多應(yīng)用場景比如資源分配、投資決策等。理解這類問題的解法不僅能幫助我們提升算法能力更能培養(yǎng)面對復(fù)雜決策時的系統(tǒng)性思維。2. 問題分析與解法思路2.1 游戲規(guī)則解析游戲規(guī)則有幾個關(guān)鍵點需要注意玩家每次可以取走前1到2M堆石子取走X堆后M會更新為max(M, X)兩位玩家都采取最優(yōu)策略愛麗絲先手這些規(guī)則決定了我們需要考慮當前剩余石子堆的狀態(tài)當前M值當前玩家的選擇對后續(xù)游戲的影響2.2 動態(tài)規(guī)劃狀態(tài)定義基于上述分析我們可以定義dp[i][m]表示當剩下第i堆到最后一堆石子時當前M值為m當前玩家能獲得的最大石子數(shù)這個狀態(tài)定義涵蓋了游戲的所有關(guān)鍵信息為后續(xù)的狀態(tài)轉(zhuǎn)移奠定了基礎(chǔ)。2.3 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移需要考慮當前玩家所有可能的取法1到2m堆并選擇對自己最有利的方案dp[i][m] max( sum(piles[i:ix]) (sum(piles[ix:]) - dp[ix][max(m,x)]) for x in range(1, 2*m1) )其中sum(piles[i:ix])是當前玩家這次取走的石子數(shù)sum(piles[ix:]) - dp[ix][max(m,x)]是當前玩家在對手采取最優(yōu)策略后能獲得的剩余石子數(shù)3. 具體實現(xiàn)與優(yōu)化3.1 基礎(chǔ)實現(xiàn)首先我們可以實現(xiàn)一個記憶化搜索的版本def stoneGameII(piles): n len(piles) prefix [0]*(n1) for i in range(n-1, -1, -1): prefix[i] prefix[i1] piles[i] from functools import lru_cache lru_cache(maxsizeNone) def dp(i, m): if i 2*m n: return prefix[i] max_stones 0 for x in range(1, 2*m1): next_m max(m, x) current prefix[i] - prefix[ix] remaining prefix[ix] - dp(ix, next_m) total current remaining if total max_stones: max_stones total return max_stones return dp(0, 1)3.2 優(yōu)化技巧前綴和優(yōu)化預(yù)先計算前綴和數(shù)組可以快速計算任意區(qū)間的和記憶化搜索使用lru_cache避免重復(fù)計算邊界條件處理當剩余石子堆數(shù)≤2m時可以直接取走所有石子3.3 時間復(fù)雜度分析狀態(tài)總數(shù)O(n^2)i從0到n-1m從1到n每個狀態(tài)的轉(zhuǎn)移O(n)x最多取n次總時間復(fù)雜度O(n^3)空間復(fù)雜度O(n^2)4. 常見問題與調(diào)試技巧4.1 常見錯誤狀態(tài)定義不完整忘記考慮M的變化邊界條件處理不當特別是當ix超過數(shù)組長度時石子數(shù)計算錯誤沒有使用前綴和導(dǎo)致計算效率低下4.2 調(diào)試建議從小規(guī)模測試用例開始驗證打印中間狀態(tài)幫助理解對比暴力解法的結(jié)果4.3 測試用例設(shè)計好的測試用例應(yīng)該包括最小規(guī)模1-2堆石子M變化較大的情況石子數(shù)分布不均勻的情況邊界條件如所有石子數(shù)相同例如[2,7,9,4,4] → 10 [1,2,3,4,5,100] → 104 [1] → 1 [1,1,1,1] → 25. 算法擴展與變種5.1 類似題目Stone Game I (LeetCode 877)Stone Game III (LeetCode 1406)Stone Game IV (LeetCode 1510)5.2 變種思考如果每次可以取1到k*M堆石子k為常數(shù)如果M的更新規(guī)則不同如果石子堆成環(huán)形排列5.3 實際應(yīng)用這類博弈動態(tài)規(guī)劃問題可以應(yīng)用于資源分配決策投資策略優(yōu)化游戲AI設(shè)計6. 個人解題心得在實際解決這個問題時我發(fā)現(xiàn)有幾個關(guān)鍵點特別重要明確狀態(tài)定義必須包含所有影響決策的關(guān)鍵信息理解對手的最優(yōu)策略這是博弈問題的核心從簡單情況入手先考慮邊界條件和小規(guī)模情況優(yōu)化計算效率前綴和和記憶化是必不可少的工具這道題教會我們面對復(fù)雜決策問題時系統(tǒng)地分解問題、定義狀態(tài)、考慮對手反應(yīng)是找到最優(yōu)解的關(guān)鍵。這種思維方式不僅在算法競賽中有用在實際生活和工作中也同樣適用。 動態(tài)規(guī)劃解石子游戲II：博弈類問題最優(yōu)策略
1. 問題背景與理解石子游戲II是LeetCode上一道經(jīng)典的動態(tài)規(guī)劃題目編號1140。這道題屬于博弈類動態(tài)規(guī)劃的典型代表考察玩家在面對游戲規(guī)則時的最優(yōu)決策能力。題目描述兩位玩家愛麗絲和鮑勃輪流從石子堆中取石子每次可以取走前X堆1 ≤ X ≤ 2M然后M變?yōu)閙ax(M, X)。游戲的目標是獲得最多的石子。這類博弈問題在實際中有諸多應(yīng)用場景比如資源分配、投資決策等。理解這類問題的解法不僅能幫助我們提升算法能力更能培養(yǎng)面對復(fù)雜決策時的系統(tǒng)性思維。2. 問題分析與解法思路2.1 游戲規(guī)則解析游戲規(guī)則有幾個關(guān)鍵點需要注意玩家每次可以取走前1到2M堆石子取走X堆后M會更新為max(M, X)兩位玩家都采取最優(yōu)策略愛麗絲先手這些規(guī)則決定了我們需要考慮當前剩余石子堆的狀態(tài)當前M值當前玩家的選擇對后續(xù)游戲的影響2.2 動態(tài)規(guī)劃狀態(tài)定義基于上述分析我們可以定義dp[i][m]表示當剩下第i堆到最后一堆石子時當前M值為m當前玩家能獲得的最大石子數(shù)這個狀態(tài)定義涵蓋了游戲的所有關(guān)鍵信息為后續(xù)的狀態(tài)轉(zhuǎn)移奠定了基礎(chǔ)。2.3 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移需要考慮當前玩家所有可能的取法1到2m堆并選擇對自己最有利的方案dp[i][m] max( sum(piles[i:ix]) (sum(piles[ix:]) - dp[ix][max(m,x)]) for x in range(1, 2*m1) )其中sum(piles[i:ix])是當前玩家這次取走的石子數(shù)sum(piles[ix:]) - dp[ix][max(m,x)]是當前玩家在對手采取最優(yōu)策略后能獲得的剩余石子數(shù)3. 具體實現(xiàn)與優(yōu)化3.1 基礎(chǔ)實現(xiàn)首先我們可以實現(xiàn)一個記憶化搜索的版本def stoneGameII(piles): n len(piles) prefix [0]*(n1) for i in range(n-1, -1, -1): prefix[i] prefix[i1] piles[i] from functools import lru_cache lru_cache(maxsizeNone) def dp(i, m): if i 2*m n: return prefix[i] max_stones 0 for x in range(1, 2*m1): next_m max(m, x) current prefix[i] - prefix[ix] remaining prefix[ix] - dp(ix, next_m) total current remaining if total max_stones: max_stones total return max_stones return dp(0, 1)3.2 優(yōu)化技巧前綴和優(yōu)化預(yù)先計算前綴和數(shù)組可以快速計算任意區(qū)間的和記憶化搜索使用lru_cache避免重復(fù)計算邊界條件處理當剩余石子堆數(shù)≤2m時可以直接取走所有石子3.3 時間復(fù)雜度分析狀態(tài)總數(shù)O(n^2)i從0到n-1m從1到n每個狀態(tài)的轉(zhuǎn)移O(n)x最多取n次總時間復(fù)雜度O(n^3)空間復(fù)雜度O(n^2)4. 常見問題與調(diào)試技巧4.1 常見錯誤狀態(tài)定義不完整忘記考慮M的變化邊界條件處理不當特別是當ix超過數(shù)組長度時石子數(shù)計算錯誤沒有使用前綴和導(dǎo)致計算效率低下4.2 調(diào)試建議從小規(guī)模測試用例開始驗證打印中間狀態(tài)幫助理解對比暴力解法的結(jié)果4.3 測試用例設(shè)計好的測試用例應(yīng)該包括最小規(guī)模1-2堆石子M變化較大的情況石子數(shù)分布不均勻的情況邊界條件如所有石子數(shù)相同例如[2,7,9,4,4] → 10 [1,2,3,4,5,100] → 104 [1] → 1 [1,1,1,1] → 25. 算法擴展與變種5.1 類似題目Stone Game I (LeetCode 877)Stone Game III (LeetCode 1406)Stone Game IV (LeetCode 1510)5.2 變種思考如果每次可以取1到k*M堆石子k為常數(shù)如果M的更新規(guī)則不同如果石子堆成環(huán)形排列5.3 實際應(yīng)用這類博弈動態(tài)規(guī)劃問題可以應(yīng)用于資源分配決策投資策略優(yōu)化游戲AI設(shè)計6. 個人解題心得在實際解決這個問題時我發(fā)現(xiàn)有幾個關(guān)鍵點特別重要明確狀態(tài)定義必須包含所有影響決策的關(guān)鍵信息理解對手的最優(yōu)策略這是博弈問題的核心從簡單情況入手先考慮邊界條件和小規(guī)模情況優(yōu)化計算效率前綴和和記憶化是必不可少的工具這道題教會我們面對復(fù)雜決策問題時系統(tǒng)地分解問題、定義狀態(tài)、考慮對手反應(yīng)是找到最優(yōu)解的關(guān)鍵。這種思維方式不僅在算法競賽中有用在實際生活和工作中也同樣適用。