2023-07-05：愛(ài)麗絲和鮑勃繼續(xù)他們的石子游戲 許多堆石子 排成一行，每堆都有正整數(shù)顆
2023-07-05：愛(ài)麗絲和鮑勃繼續(xù)他們的石子游戲
許多堆石子 排成一行，每堆都有正整數(shù)顆石子 piles[i]
游戲以誰(shuí)手中的石子最多來(lái)決出勝負(fù)。
愛(ài)麗絲和鮑勃輪流進(jìn)行，愛(ài)麗絲先開(kāi)始。最初，M = 1。
在每個(gè)玩家的回合中，該玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M
然后，令 M = max(M, X)。
游戲一直持續(xù)到所有石子都被拿走。
假設(shè)愛(ài)麗絲和鮑勃都發(fā)揮出最佳水平W
返回愛(ài)麗絲可以得到的最大數(shù)量的石頭。
輸入：piles = [2,7,9,4,4]。
輸出：10。
答案2023-07-05：
1.算法 stoneGameII1：暴力方法
??首先定義函數(shù) stoneGameII1，接收一個(gè)石子堆的切片 piles 作為參數(shù)，并返回愛(ài)麗絲可以得到的最大數(shù)量的石頭。
??在函數(shù) stoneGameII1 中調(diào)用函數(shù) first1，并傳入初始參數(shù) piles、index=0（表示當(dāng)前石子堆的索引）、m=1（表示當(dāng)前的 M 值）。
??函數(shù) first1 的作用是計(jì)算愛(ài)麗絲在當(dāng)前石子堆的狀態(tài)下的最優(yōu)解。如果當(dāng)前石子堆的索引達(dá)到了最后一個(gè)位置（即 index == len(piles)），則返回 0（石子已經(jīng)全部取完）。
??否則，初始化變量 best = 0（當(dāng)前的最優(yōu)解）和 pre = 0（當(dāng)前已經(jīng)取走的石子數(shù)量）。
??開(kāi)始一個(gè)循環(huán)，從當(dāng)前索引開(kāi)始遍歷石子堆（i = index），并且用變量 j 記錄當(dāng)前取走的石子堆的數(shù)量（初始值為 1）。
??在循環(huán)中，更新變量 pre = pre + piles[i]，即計(jì)算當(dāng)前的已取走的石子數(shù)量。
??然后，根據(jù)當(dāng)前的石子堆狀態(tài)以及剩余可取的石子堆的數(shù)量（int(math.Max(float64(j), float64(m)))），調(diào)用函數(shù) second1，并傳入相應(yīng)的參數(shù)，計(jì)算愛(ài)麗絲在下一輪的最優(yōu)解。
??更新變量 best = int(math.Max(float64(best), float64(pre+second1(piles, i+1, int(math.Max(float64(j), float64(m)))))))，即取當(dāng)前輪最優(yōu)解和已取走的石子數(shù)量之和的較大值作為當(dāng)前的最優(yōu)解。
??循環(huán)結(jié)束后，返回變量 best。
函數(shù) second1 的作用是計(jì)算鮑勃在當(dāng)前石子堆的狀態(tài)下的最優(yōu)解，其過(guò)程與函數(shù) first1 類(lèi)似。
??首先判斷是否遍歷到了最后一個(gè)石子堆，如果是，則返回 0（石子已全部取走）。
??否則，初始化變量 worse = math.MaxInt64（當(dāng)前的最差解）。
??開(kāi)始一個(gè)循環(huán)，從當(dāng)前索引開(kāi)始遍歷石子堆，并用變量 j 記錄當(dāng)前取走的石子堆的數(shù)量（初始值為 1）。
??在循環(huán)中，更新變量 worse = int(math.Min(float64(worse), float64(first1(piles, i+1, int(math.Max(float64(j), float64(m)))))))，即取當(dāng)前輪最差解和已取走的石子數(shù)量之和的較小值作為當(dāng)前的最差解。
??循環(huán)結(jié)束后，返回變量 worse。
2.算法 stoneGameII2：記憶化搜索
??首先定義函數(shù) stoneGameII2，接收一個(gè)石子堆的切片 piles 作為參數(shù)，并返回愛(ài)麗絲可以得到的最大數(shù)量的石頭。
??在函數(shù) stoneGameII2 中，首先初始化變量 n 為石子堆的數(shù)量，創(chuàng)建兩個(gè)二維切片 f 和 s，用于存儲(chǔ)記憶化搜索的結(jié)果。
??利用循環(huán)，初始化 f 和 s 的值為 -1。
??調(diào)用函數(shù) first2，并傳入初始參數(shù) piles、index=0（表示當(dāng)前石子堆的索引）、m=1（表示當(dāng)前的 M 值）、f 和 s。
??函數(shù) first2 的作用是計(jì)算愛(ài)麗絲在當(dāng)前石子堆的狀態(tài)下的最優(yōu)解，其過(guò)程類(lèi)似函數(shù) first1，但加入了記憶化搜索的機(jī)制。
??首先判斷是否已經(jīng)計(jì)算過(guò)該狀態(tài)的結(jié)果，如果是，則直接返回存儲(chǔ)的結(jié)果 f[index][m]。
??否則，繼續(xù)計(jì)算最優(yōu)解。
??在計(jì)算過(guò)程中，每一輪的最優(yōu)解都會(huì)存儲(chǔ)在 f[index][m]，以避免重復(fù)計(jì)算。
??在循環(huán)中，需要調(diào)用函數(shù) second2，傳入相應(yīng)的參數(shù)，計(jì)算鮑勃在當(dāng)前石子堆的狀態(tài)下的最優(yōu)解，并存儲(chǔ)在 s[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))] 中。
??循環(huán)結(jié)束后，將最優(yōu)解保存到 f[index][m] 中，并返回最優(yōu)解。
函數(shù) second2 的作用是計(jì)算鮑勃在當(dāng)前石子堆的狀態(tài)下的最優(yōu)解，與函數(shù) second1 類(lèi)似，但加入了記憶化搜索的機(jī)制。
??首先判斷是否已經(jīng)計(jì)算過(guò)該狀態(tài)的結(jié)果，如果是，則直接返回存儲(chǔ)的結(jié)果 s[index][m]。
??否則，繼續(xù)計(jì)算最優(yōu)解。
??在計(jì)算過(guò)程中，每一輪的最優(yōu)解都會(huì)存儲(chǔ)在 s[index][m]，以避免重復(fù)計(jì)算。
??循環(huán)結(jié)束后，將最優(yōu)解保存到 s[index][m] 中，并返回最優(yōu)解。
3.算法 stoneGameII3：嚴(yán)格位置依賴(lài)的動(dòng)態(tài)規(guī)劃，一張表的版本
??首先定義函數(shù) stoneGameII3，接收一個(gè)石子堆的切片 piles 作為參數(shù)，并返回愛(ài)麗絲可以得到的最大數(shù)量的石頭。
??在函數(shù) stoneGameII3 中，首先初始化變量 n 為石子堆的數(shù)量，創(chuàng)建兩個(gè)二維切片 f 和 s，表示愛(ài)麗絲和鮑勃在每個(gè)石子堆的狀態(tài)下的最優(yōu)解。
??利用循環(huán)，初始化 f 和 s 的值為 0。
??初始化變量 sum = 0，用于記錄累計(jì)的石子數(shù)。
??從最后一個(gè)石子堆開(kāi)始循環(huán)，更新變量 sum = sum + piles[index]，即計(jì)算當(dāng)前的累計(jì)石子數(shù)。
??在循環(huán)中，根據(jù)動(dòng)態(tài)規(guī)劃的思想，計(jì)算愛(ài)麗絲和鮑勃的最優(yōu)解。
??首先計(jì)算愛(ài)麗絲在當(dāng)前石子堆狀態(tài)下的最優(yōu)解。
??聲明變量 best = 0，表示當(dāng)前的最優(yōu)解。
??聲明變量 pre = 0，表示當(dāng)前已經(jīng)取走的石子數(shù)量。
??在循環(huán)中，用變量 j 記錄當(dāng)前取走的石子堆的數(shù)量（初始值為 1）。
??在循環(huán)中，更新變量 pre = pre + piles[i]，即計(jì)算當(dāng)前的已取走的石子數(shù)量。
??根據(jù)當(dāng)前的石子堆狀態(tài)以及剩余可取的石子堆的數(shù)量（int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m))))）），計(jì)算愛(ài)麗絲在下一輪的最優(yōu)解 s[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))]。
??更新變量 best = int(math.Max(float64(best), float64(pre+s[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))])))，取當(dāng)前輪最優(yōu)解和已取走的石子數(shù)量之和的較大值作為當(dāng)前的最優(yōu)解。
??計(jì)算鮑勃在當(dāng)前石子堆狀態(tài)下的最優(yōu)解。
??聲明變量 worse = math.MaxInt64，表示當(dāng)前的最差解。
??在循環(huán)中，用變量 j 記錄當(dāng)前取走的石子堆的數(shù)量（初始值為 1）。
??在循環(huán)中，更新變量 worse = int(math.Min(float64(worse), float64(f[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))])))，取當(dāng)前輪最差解和已取走的石子數(shù)量之和的較小值作為當(dāng)前的最差解。
??循環(huán)結(jié)束后，更新 f[index][m] = best 和 s[index][m] = worse。
??返回 f[0][1]，即愛(ài)麗絲在初始狀態(tài)下的最優(yōu)解。
4.算法 stoneGameII4：嚴(yán)格位置依賴(lài)的動(dòng)態(tài)規(guī)劃
??首先定義函數(shù) stoneGameII4，接收一個(gè)石子堆的切片 piles 作為參數(shù)，并返回愛(ài)麗絲可以得到的最大數(shù)量的石頭。
??在函數(shù) stoneGameII4 中，首先初始化變量 n 為石子堆的數(shù)量，創(chuàng)建一個(gè)二維切片 dp，用于存儲(chǔ)動(dòng)態(tài)規(guī)劃的結(jié)果。
??利用循環(huán)，初始化 dp 的值為 0。
??初始化變量 sum = 0，用于記錄累計(jì)的石子數(shù)。
??從最后一個(gè)石子堆開(kāi)始循環(huán)，更新變量 sum = sum + piles[i]，即計(jì)算當(dāng)前的累計(jì)石子數(shù)。
??在循環(huán)中，根據(jù)動(dòng)態(tài)規(guī)劃的思想，計(jì)算愛(ài)麗絲的最優(yōu)。
stoneGameII1的時(shí)間復(fù)雜度為$O(2^n)$，空間復(fù)雜度為$O(n)$。
stoneGameII2的時(shí)間復(fù)雜度為$O(n^3)$，空間復(fù)雜度為$O(n^2)$。
stoneGameII3的時(shí)間復(fù)雜度為$O(n^3)$，空間復(fù)雜度為$O(n^2)$。
stoneGameII4的時(shí)間復(fù)雜度為$O(n^2)$，空間復(fù)雜度為$O(n)$。
go完整代碼如下：
package?main
import?(
????"fmt"
????"math"
)
//?暴力方法
func?stoneGameII1(piles?[]int)?int?{
????return?first1(piles,?0,?1)
}
func?first1(piles?[]int,?index,?m?int)?int?{
????if?index?==?len(piles)?{
????????return?0
????}
????best?:=?0
????pre?:=?0
????for?i,?j?:=?index,?1;?i?<?len(piles)?&&?j?<=?2*m;?i,?j?=?i+1,?j+1?{
????????pre?+=?piles[i]
????????best?=?int(math.Max(float64(best),?float64(pre+second1(piles,?i+1,?int(math.Max(float64(j),?float64(m)))))))
????}
????return?best
}
func?second1(piles?[]int,?index,?m?int)?int?{
????if?index?==?len(piles)?{
????????return?0
????}
????worse?:=?math.MaxInt64
????for?i,?j?:=?index,?1;?i?<?len(piles)?&&?j?<=?2*m;?i,?j?=?i+1,?j+1?{
????????worse?=?int(math.Min(float64(worse),?float64(first1(piles,?i+1,?int(math.Max(float64(j),?float64(m)))))))
????}
????return?worse
}
//?記憶化搜索
func?stoneGameII2(piles?[]int)?int?{
????n?:=?len(piles)
????f?:=?make([][]int,?n)
????s?:=?make([][]int,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????f[i]?=?make([]int,?n+1)
????????s[i]?=?make([]int,?n+1)
????????for?j?:=?0;?j?<=?n;?j++?{
????????????f[i][j]?=?-1
????????????s[i][j]?=?-1
????????}
????}
????return?first2(piles,?0,?1,?f,?s)
}
func?first2(piles?[]int,?index,?m?int,?f,?s?[][]int)?int?{
????if?index?==?len(piles)?{
????????return?0
????}
????if?f[index][m]?!=?-1?{
????????return?f[index][m]
????}
????best?:=?0
????pre?:=?0
????for?i,?j?:=?index,?1;?i?<?len(piles)?&&?j?<=?2*m;?i,?j?=?i+1,?j+1?{
????????pre?+=?piles[i]
????????best?=?int(math.Max(float64(best),?float64(pre+second2(piles,?i+1,?int(math.Min(float64(len(piles)),?float64(math.Max(float64(j),?float64(m))))),?f,?s))))
????}
????f[index][m]?=?best
????return?best
}
func?second2(piles?[]int,?index,?m?int,?f,?s?[][]int)?int?{
????if?index?==?len(piles)?{
????????return?0
????}
????if?s[index][m]?!=?-1?{
????????return?s[index][m]
????}
????worse?:=?math.MaxInt64
????for?i,?j?:=?index,?1;?i?<?len(piles)?&&?j?<=?2*m;?i,?j?=?i+1,?j+1?{
????????worse?=?int(math.Min(float64(worse),?float64(first2(piles,?i+1,?int(math.Min(float64(len(piles)),?float64(math.Max(float64(j),?float64(m))))),?f,?s))))
????}
????s[index][m]?=?worse
????return?worse
}
//?嚴(yán)格位置依賴(lài)的動(dòng)態(tài)規(guī)劃，一張表的版本
func?stoneGameII3(piles?[]int)?int?{
????n?:=?len(piles)
????f?:=?make([][]int,?n+1)
????s?:=?make([][]int,?n+1)
????for?i?:=?0;?i?<=?n;?i++?{
????????f[i]?=?make([]int,?n+1)
????????s[i]?=?make([]int,?n+1)
????}
????sum?:=?0
????for?index?:=?n?-?1;?index?>=?0;?index--?{
????????sum?+=?piles[index]
????????for?m?:=?1;?m?<=?n;?m++?{
????????????best?:=?0
????????????pre?:=?0
????????????for?i,?j?:=?index,?1;?i?<?len(piles)?&&?j?<=?2*m;?i,?j?=?i+1,?j+1?{
????????????????pre?+=?piles[i]
????????????????best?=?int(math.Max(float64(best),?float64(pre+s[i+1][int(math.Min(float64(n),?float64(math.Max(float64(j),?float64(m)))))])))
????????????}
????????????f[index][m]?=?best
????????????worse?:=?math.MaxInt64
????????????for?i,?j?:=?index,?1;?i?<?len(piles)?&&?j?<=?2*m;?i,?j?=?i+1,?j+1?{
????????????????worse?=?int(math.Min(float64(worse),?float64(f[i+1][int(math.Min(float64(n),?float64(math.Max(float64(j),?float64(m)))))])))
????????????}
????????????s[index][m]?=?worse
????????}
????}
????return?f[0][1]
}
//?嚴(yán)格位置依賴(lài)的動(dòng)態(tài)規(guī)劃
func?stoneGameII4(piles?[]int)?int?{
????n?:=?len(piles)
????sum?:=?0
????dp?:=?make([][]int,?n)
????for?i?:=?range?dp?{
????????dp[i]?=?make([]int,?n+1)
????}
????for?i?:=?n?-?1;?i?>=?0;?i--?{
????????sum?+=?piles[i]
????????for?m?:=?1;?m?<=?n;?m++?{
????????????if?i+2*m?>=?n?{
????????????????dp[i][m]?=?sum
????????????}?else?{
????????????????nextMin?:=?math.MaxInt64
????????????????for?x?:=?1;?x?<=?2*m;?x++?{
????????????????????nextMin?=?int(math.Min(float64(nextMin),?float64(dp[i+x][int(math.Max(float64(m),?float64(x)))])))
????????????????}
????????????????dp[i][m]?=?sum?-?nextMin
????????????}
????????}
????}
????return?dp[0][1]
}
func?main()?{
????piles?:=?[]int{2,?7,?9,?4,?4}
????fmt.Println("stoneGameII1:",?stoneGameII1(piles))
????fmt.Println("stoneGameII2:",?stoneGameII2(piles))
????fmt.Println("stoneGameII3:",?stoneGameII3(piles))
????fmt.Println("stoneGameII4:",?stoneGameII4(piles))
}
