1140。石頭游戲ii
難度：中等
主題： 數(shù)組、數(shù)學(xué)、動態(tài)規(guī)劃、前綴和、博弈論
愛麗絲和鮑勃繼續(xù)玩石頭堆游戲。 有許多堆排成一排，每堆有正整數(shù)個石子piles[i]。 游戲的目標(biāo)是以最多的石子結(jié)束。
愛麗絲和鮑勃輪流，愛麗絲先開始。 最初，m = 1.
在每個玩家的回合中，該玩家可以拿走第一個剩余 x 堆中的所有石頭，其中 1
游戲繼續(xù)進(jìn)行，直到所有的石子都被拿走。
假設(shè)愛麗絲和鮑勃發(fā)揮最佳，返回愛麗絲可以獲得的最大石頭數(shù)量。
示例1：
輸入： 樁 = [2,7,9,4,4]
輸出： 10
解釋： 如果 alice 一開始拿了一堆，bob 拿了兩堆，然后 alice 又拿了 2 堆。愛麗絲總共可以獲得 2 + 4 + 4 = 10 堆。如果愛麗絲一開始拿了兩堆，那么鮑勃就可以拿走剩下的三堆。在這種情況下，愛麗絲總共得到 2 + 7 = 9 堆。所以我們返回 10，因?yàn)樗蟆?/p>
示例2：
輸入： 樁 = [1,2,3,4,5,100]
輸出： 104
限制：
1
1 4
提示：
-
使用動態(tài)規(guī)劃：對于給定 m 的piles[i:] 的答案，狀態(tài)為 (i, m)。
解決方案：
我們需要使用動態(tài)規(guī)劃來找到如果雙方都發(fā)揮最佳狀態(tài)，alice 可以獲得的最大石頭數(shù)量。以下是開發(fā)解決方案的分步方法：
定義狀態(tài)和轉(zhuǎn)換：
定義一個 2d dp 數(shù)組，其中 dp[i][m] 表示 alice 從第 i 堆開始可以收集的最大石頭，最大拾取限制為 m。
使用前綴和數(shù)組來高效計(jì)算子數(shù)組中石頭的總和。
基本案例：
如果沒有剩下的石頭可供采摘，則得分為 0。
遞歸案例：
對于每一堆 i 和最大允許拾取 m ，通過考慮所有可能的移動（取 1 到 2m 堆）來計(jì)算 alice 可以收集的最大石頭。
轉(zhuǎn)換函數(shù)：
對于愛麗絲可以挑選的每種可能的堆數(shù)，計(jì)算愛麗絲可以獲得的石頭總數(shù)，并使用未來狀態(tài)的結(jié)果來決定最佳移動。
讓我們用 php 實(shí)現(xiàn)這個解決方案：1140。石頭游戲ii
<?php // Example usage $solution = new Solution(); $piles1 = [2, 7, 9, 4, 4]; $piles2 = [1, 2, 3, 4, 5, 100]; echo $solution->stoneGameII($piles1) . "\n"; // Output: 10 echo $solution->stoneGameII($piles2) . "\n"; // Output: 104 ?>
登錄后復(fù)制
解釋：
前綴總和計(jì)算：這有助于快速計(jì)算任意一堆 i 到 j 中的石子的總和。
dp 數(shù)組初始化： dp[i][m] 保存 alice 從 i 堆開始可以獲取的最大石頭，最大拾取限制為 m。
動態(tài)編程轉(zhuǎn)換： 對于每一堆和 m，通過迭代她可以獲取的可能堆數(shù)并相應(yīng)更新 dp 數(shù)組來計(jì)算 alice 可以收集的最大石頭。
這種方法確保了解決方案的高效計(jì)算，利用動態(tài)規(guī)劃來避免冗余計(jì)算。
聯(lián)系鏈接
如果您發(fā)現(xiàn)本系列有幫助，請考慮在 github 上給存儲庫 一顆星，或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子?。您的支持對我來說意義重大！
如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：
領(lǐng)英
github
