2023-05-09：石子游戲中，愛麗絲和鮑勃輪流進行自己的回合，愛麗絲先開始 。 有 n 塊
2023-05-09：石子游戲中，愛麗絲和鮑勃輪流進行自己的回合，愛麗絲先開始 。 有 n 塊石子排成一排。 每個玩家的回合中，可以從行中 移除 最左邊的石頭或最右邊的石頭， 并獲得與該行中剩余石頭值之 和 相等的得分。當沒有石頭可移除時，得分較高者獲勝。 鮑勃發(fā)現(xiàn)他總是輸?shù)粲螒颍蓱z的鮑勃，他總是輸）， 所以他決定盡力 減小得分的差值 。愛麗絲的目標是最大限度地 擴大得分的差值 。 給你一個整數(shù)數(shù)組 stones ，其中 stones[i] 表示 從左邊開始 的第 i 個石頭的值， 如果愛麗絲和鮑勃都 發(fā)揮出最佳水平 ，請返回他們 得分的差值 。 輸入：stones = [5,3,1,4,2] 。 輸出：6 。
答案2023-05-09：
該問題的解法有多種，下面分別對三個函數(shù)的實現(xiàn)過程進行詳細描述。
1.遞歸版
該函數(shù)使用遞歸實現(xiàn)了石子游戲。首先計算出整個石子數(shù)組的和sum，然后調(diào)用f函數(shù)獲取Alice獲得的最大得分，再調(diào)用s函數(shù)獲取Bob獲得的最大得分，最終計算出差值并返回。
f函數(shù)表示當前輪到Alice操作，從L位置取走一個石頭或從R位置取走一個石頭的情況下，Alice能獲得的最大得分。將這兩種情況所獲得的得分與對手（Bob）相比較，選擇更優(yōu)的方案。其中，對手的得分由s函數(shù)計算。
s函數(shù)表示當前輪到Bob操作，在剩余石子中選擇一個最優(yōu)的石子讓Alice取走，并計算自己的得分。此處需要注意，當前是Bob在操作，但是得分卻是Alice決定的，因為Alice可以在自己的回合中選擇拿走哪一塊石頭，進而影響B(tài)ob的得分。
時間復(fù)雜度為$O(2^n)$，空間復(fù)雜度為$O(n)$，其中n是石頭的數(shù)量。
因為在每一層遞歸中，都會有兩種分支需要繼續(xù)遞歸下去，所以總共會有2^n個葉子節(jié)點。另外，由于遞歸的深度最多為n層，所以需要O(n)的?？臻g來存儲每一層遞歸的狀態(tài)。
2.動態(tài)規(guī)劃版
該函數(shù)使用動態(tài)規(guī)劃實現(xiàn)了石子游戲。首先計算出整個石子數(shù)組的前綴和presum，然后定義兩個二維數(shù)組dpf和dps。其中，dpf[i][j]表示當只剩下第i到第j塊石頭時，先手（即Alice）能夠獲得的最大得分；dps[i][j]表示當只剩下第i到第j塊石頭時，后手（即Bob）能夠獲得的最大得分。
接著，從右下角開始倒序遍歷數(shù)組，計算出dpf和dps數(shù)組的值。具體計算方法如下：
??當前輪到先手操作，先手可以選擇拿走第i塊石頭或第j塊石頭。如果先手拿走了第i塊石頭，則后手只能在第i+1到第j塊石頭中進行選擇，在這種情況下，先手能夠獲得的得分為sumLR - stones[i] + dps[L+1][R]，其中sumLR表示第i到第j塊石頭的和，dps[L+1][R]表示后手在第i+1到第j塊石頭中能夠獲得的最大得分。如果先手拿走了第j塊石頭，則后手只能在第i到第j-1塊石頭中進行選擇，在這種情況下，先手能夠獲得的得分為sumLR - stones[j] + dps[L][R-1]，其中dps[L][R-1]表示后手在第i到第j-1塊石頭中能夠獲得的最大得分。因為是先手行動，所以先手最終能夠獲得的得分為這兩種情況中的較大值。
??當前輪到后手操作，后手只能在剩余的石頭中選擇一個最優(yōu)的石頭讓先手取走，并計算自己的得分。即后手能夠獲得的最大得分為sumLR - stones[i] + dps[L+1][R]或sumLR - stones[j] + dps[L][R-1]中的較大值。
最終，返回dpf[0][n-1] - dps[0][n-1]的絕對值，即Alice和Bob得分的差值。
時間復(fù)雜度為$O(n^2)$，空間復(fù)雜度為$O(n^2)$，其中n是石頭的數(shù)量。
計算dpf和dps數(shù)組的過程需要遍歷所有的狀態(tài)，其中每個狀態(tài)需要O(1)的時間進行計算，因此總時間復(fù)雜度為$O(n^2)$。另外，因為需要維護兩個二維數(shù)組，所以需要O(n^2)的額外空間來存儲這些狀態(tài)。
3.另一種嘗試
該函數(shù)使用動態(tài)規(guī)劃實現(xiàn)了石子游戲。定義dp[len][i]表示從第i塊石頭出發(fā)，當長度為len時，Alice能比Bob多多少分？其中所謂的長度為len是指剩下的石頭數(shù)量。例如，假設(shè)當前還剩下5塊石頭，即len=5，則dp[5][i]表示從第i塊石頭出發(fā)，當只剩下5塊石頭時，Alice能比Bob多多少分。
首先，如果剩余的石頭數(shù)量為偶數(shù)，那么Alice一定會選擇先手，并且每次都取走價值最高的石頭。因此，對于所有的i，dp[1][i]都等于stones[i]。對于剩余的情況，我們需要使用動態(tài)規(guī)劃來計算dp[len][i]。具體來說，我們可以考慮當前輪到先手操作，他可以選擇拿走第i塊石頭或第j塊石頭，然后根據(jù)后續(xù)狀態(tài)遞歸計算。
因為狀態(tài)之間存在依賴關(guān)系，所以我們可以倒序遍歷數(shù)組，從右下角開始計算。具體來說，我們可以按照如下方式進行狀態(tài)轉(zhuǎn)移：
??如果當前是先手操作，那么他可以選擇拿走第i塊石頭或第j塊石頭。如果他選擇了第i塊石頭，那么剩下的石頭數(shù)量就變成了len-1，并且下一個人變成了后手，此時當前狀態(tài)的價值為stones[i]-dp[len-1][i+1]；如果他選擇了第j塊石頭，那么剩下的石頭數(shù)量也變成了len-1，但是下一個人仍然是后手，此時當前狀態(tài)的價值為stones[j]-dp[len-1][i]。因為是先手行動，所以他會選擇讓自己的得分更高，即dp[len][i]=max(stones[i]-dp[len-1][i+1], stones[j]-dp[len-1][i])。
??如果當前是后手操作，那么他只能在剩余的石頭中選擇一個最優(yōu)的石頭讓先手取走，并計算自己的得分。具體來說，如果他選擇了第i塊石頭，那么剩余的石頭數(shù)量就變成了len-1，并且下一個人變成了先手，此時當前狀態(tài)的價值為-dp[len-1][i+1]；如果他選擇了第j塊石頭，那么剩余的石頭數(shù)量也變成了len-1，但是下一個人仍然是先手，此時當前狀態(tài)的價值為-dp[len-1][i]。因為是后手行動，所以他會選擇讓自己的得分更高，即dp[len][i]=min(-dp[len-1][i+1], -dp[len-1][i])。
最終，我們返回dp[0][n-1]的值，即從第0塊石頭出發(fā)，當長度為n時，Alice能比Bob多多少分。
時間復(fù)雜度為$O(n^2)$，空間復(fù)雜度為$O(n^2)$，其中n是石頭的數(shù)量。
計算dp數(shù)組的過程需要遍歷所有的狀態(tài)，其中每個狀態(tài)需要O(1)的時間進行計算，因此總時間復(fù)雜度為$O(n^2)$。另外，由于需要維護一個二維數(shù)組，所以需要$O(n^2)$的額外空間來存儲這些狀態(tài)。
三種算法總結(jié)
綜上所述，第二種和第三種方法的時間復(fù)雜度和空間復(fù)雜度相同，都比第一種方法更加高效。在實際使用中，我們應(yīng)該優(yōu)先選擇動態(tài)規(guī)劃算法來解決這類問題，因為它能夠在多項式時間內(nèi)求解，而遞歸算法則往往會導致指數(shù)級別的復(fù)雜度。
go完整代碼如下：
package?main
import?(
????"fmt"
)
//?遞歸版
func?stoneGameVII1(stones?[]int)?int?{
????sum?:=?0
????for?_,?num?:=?range?stones?{
????????sum?+=?num
????}
????alice?:=?f(stones,?sum,?0,?len(stones)-1)
????bob?:=?s(stones,?sum,?0,?len(stones)-1)
????return?abs(alice?-?bob)
}
//?先手
func?f(stones?[]int,?sum,?L,?R?int)?int?{
????if?L?==?R?{?//?只能一塊兒了！
????????return?0
????}
????//?L為起點
????p1?:=?sum?-?stones[L]?+?s(stones,?sum-stones[L],?L+1,?R)
????against1?:=?f(stones,?sum-stones[L],?L+1,?R)
????//?R為終點
????p2?:=?sum?-?stones[R]?+?s(stones,?sum-stones[R],?L,?R-1)
????against2?:=?f(stones,?sum-stones[R],?L,?R-1)
????if?p1-against1?>?p2-against2?{
????????return?p1
????}
????return?p2
}
//?后手！
func?s(stones?[]int,?sum,?L,?R?int)?int?{
????if?L?==?R?{
????????return?0
????}
????//?當前的是后手
????//?對手，先手！
????against1?:=?sum?-?stones[L]?+?s(stones,?sum-stones[L],?L+1,?R)
????//?當前用戶的得分！后手！是對手決定的！
????get1?:=?f(stones,?sum-stones[L],?L+1,?R)
????against2?:=?sum?-?stones[R]?+?s(stones,?sum-stones[R],?L,?R-1)
????get2?:=?f(stones,?sum-stones[R],?L,?R-1)
????if?against1-get1?>?against2-get2?{
????????return?get1
????}
????return?get2
}
//?動態(tài)規(guī)劃版
func?stoneGameVII2(stones?[]int)?int?{
????n?:=?len(stones)
????presum?:=?make([]int,?n+1)
????for?i?:=?0;?i?<?n;?i++?{
????????presum[i+1]?=?presum[i]?+?stones[i]
????}
????dpf?:=?make([][]int,?n)
????dps?:=?make([][]int,?n)
????for?i?:=?range?dpf?{
????????dpf[i]?=?make([]int,?n)
????????dps[i]?=?make([]int,?n)
????}
????for?L?:=?n?-?2;?L?>=?0;?L--?{
????????for?R?:=?L?+?1;?R?<?n;?R++?{
????????????sumLR?:=?presum[R+1]?-?presum[L]
????????????a?:=?sumLR?-?stones[L]?+?dps[L+1][R]
????????????b?:=?dpf[L+1][R]
????????????c?:=?sumLR?-?stones[R]?+?dps[L][R-1]
????????????d?:=?dpf[L][R-1]
????????????if?a-b?>?c-d?{
????????????????dpf[L][R]?=?a
????????????????dps[L][R]?=?b
????????????}?else?{
????????????????dpf[L][R]?=?c
????????????????dps[L][R]?=?d
????????????}
????????}
????}
????return?abs(dpf[0][n-1]?-?dps[0][n-1])
}
//?另一種嘗試?+?static動態(tài)規(guī)劃表?+?空間壓縮?+?盡量優(yōu)化
//?dp[len][i]?:?從i出發(fā)，當長度為len的情況下，Alice能比Bob多多少分？
//?要注意結(jié)算時機！這是這種嘗試的核心！
var?dp?[1000]int
//?時間復(fù)雜度和剛才講的一樣！
func?stoneGameVII3(stones?[]int)?int?{
????n?:=?len(stones)
????for?i?:=?0;?i?<?n;?i++?{
????????dp[i]?=?0
????}
????if?n%2?==?0?{
????????for?i?:=?0;?i?<?n;?i++?{
????????????dp[i]?=?stones[i]
????????}
????}
????alicePick?:=?n%2?==?0
????for?len?:=?2;?len?<=?n;?len,?alicePick?=?len+1,?!alicePick?{
????????for?i,?j?:=?0,?len-1;?j?<?n;?i,?j?=?i+1,?j+1?{
????????????if?alicePick?{
????????????????dp[i]?=?max(dp[i],?dp[i+1])
????????????}?else?{
????????????????dp[i]?=?min(dp[i]+stones[j],?stones[i]+dp[i+1])
????????????}
????????}
????}
????return?dp[0]
}
func?abs(a?int)?int?{
????if?a?<?0?{
????????return?-a
????}
????return?a
}
func?max(a,?b?int)?int?{
????if?a?>?b?{
????????return?a
????}
????return?b
}
func?min(a,?b?int)?int?{
????if?a?<?b?{
????????return?a
????}
????return?b
}
func?main()?{
????stones?:=?[]int{5,?3,?1,?4,?2}
????fmt.Println(stoneGameVII1(stones))
????fmt.Println(stoneGameVII2(stones))
????fmt.Println(stoneGameVII3(stones))
}
rust完整代碼如下：
fn?main()?{
????let?stones?=?vec![5,?3,?1,?4,?2];
????let?result?=?stone_game_vii1(stones);
????println!("{}",?result);
????let?stones?=?vec![5,?3,?1,?4,?2];
????let?result?=?stone_game_vii2(stones);
????println!("{}",?result);
????let?stones?=?vec![5,?3,?1,?4,?2];
????let?result?=?stone_game_vii3(stones);
????println!("{}",?result);
}
fn?stone_game_vii1(stones:?Vec<i32>)?->?i32?{
????let?sum:?i32?=?stones.iter().sum();
????let?alice?=?f(&stones,?sum,?0,?stones.len()?-?1);
????let?bob?=?s(&stones,?sum,?0,?stones.len()?-?1);
????(alice?-?bob).abs()
}
//?先手
fn?f(stones:?&Vec<i32>,?sum:?i32,?l:?usize,?r:?usize)?->?i32?{
????if?l?==?r?{
????????return?0;
????}
????//?p1
????let?p1?=?sum?-?stones[l]?+?s(stones,?sum?-?stones[l],?l?+?1,?r);
????let?against1?=?f(stones,?sum?-?stones[l],?l?+?1,?r);
????//?p2
????let?p2?=?sum?-?stones[r]?+?s(stones,?sum?-?stones[r],?l,?r?-?1);
????let?against2?=?f(stones,?sum?-?stones[r],?l,?r?-?1);
????if?p1?-?against1?>?p2?-?against2?{
????????p1
????}?else?{
????????p2
????}
}
//?后手
fn?s(stones:?&Vec<i32>,?sum:?i32,?l:?usize,?r:?usize)?->?i32?{
????if?l?==?r?{
????????return?0;
????}
????let?against1?=?sum?-?stones[l]?+?s(stones,?sum?-?stones[l],?l?+?1,?r);
????let?get1?=?f(stones,?sum?-?stones[l],?l?+?1,?r);
????let?against2?=?sum?-?stones[r]?+?s(stones,?sum?-?stones[r],?l,?r?-?1);
????let?get2?=?f(stones,?sum?-?stones[r],?l,?r?-?1);
????if?against1?-?get1?>?against2?-?get2?{
????????get1
????}?else?{
????????get2
????}
}
fn?stone_game_vii2(stones:?Vec<i32>)?->?i32?{
????let?n?=?stones.len();
????let?mut?presum?=?vec![0;?n?+?1];
????for?i?in?0..n?{
????????presum[i?+?1]?=?presum[i]?+?stones[i];
????}
????let?mut?dpf?=?vec![vec![0;?n];?n];
????let?mut?dps?=?vec![vec![0;?n];?n];
????for?l?in?(0..n?-?1).rev()?{
????????for?r?in?l?+?1..n?{
????????????let?sum_lr?=?presum[r?+?1]?-?presum[l];
????????????let?a?=?sum_lr?-?stones[l]?+?dps[l?+?1][r];
????????????let?b?=?dpf[l?+?1][r];
????????????let?c?=?sum_lr?-?stones[r]?+?dps[l][r?-?1];
????????????let?d?=?dpf[l][r?-?1];
????????????dpf[l][r]?=?if?a?-?b?>?c?-?d?{?a?}?else?{?c?};
????????????dps[l][r]?=?if?a?-?b?>?c?-?d?{?b?}?else?{?d?};
????????}
????}
????(dpf[0][n?-?1]?-?dps[0][n?-?1]).abs()
}
fn?stone_game_vii3(stones:?Vec<i32>)?->?i32?{
????let?n?=?stones.len();
????let?mut?dp?=?unsafe?{?DP?};
????dp.iter_mut().take(n).for_each(|x|?*x?=?0);
????if?n?%?2?==?0?{
????????for?i?in?0..n?{
????????????dp[i]?=?stones[i];
????????}
????}
????let?mut?alice_pick?=?n?%?2?==?0;
????for?len?in?2..=n?{
????????for?i?in?0..=(n?-?len)?{
????????????let?j?=?i?+?len?-?1;
????????????dp[i]?=?if?alice_pick?{
????????????????dp[i].max(dp[i?+?1])
????????????}?else?{
????????????????(dp[i]?+?stones[j]).min(stones[i]?+?dp[i?+?1])
????????????};
????????}
????????alice_pick?=?!alice_pick;
????}
????dp[0]
}
static?mut?DP:?[i32;?1000]?=?[0;?1000];
