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的得分。

時間復雜度為，空間復雜度為，其中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得分的差值。

時間復雜度為，空間復雜度為，其中n是石頭的數(shù)量。

計算dpf和dps數(shù)組的過程需要遍歷所有的狀態(tài)，其中每個狀態(tài)需要O(1)的時間進行計算，因此總時間復雜度為。另外，因為需要維護兩個二維數(shù)組，所以需要O(n^2)的額外空間來存儲這些狀態(tài)。

3.另一種嘗試

該函數(shù)使用動態(tài)規(guī)劃實現(xiàn)了石子游戲。定義dp[len][i]表示從第i塊石頭出發(fā)，當長度為len時，Alice能比Bob多多少分？其中所謂的長度為len是指剩下的石頭數(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)之間存在依賴關系，所以我們可以倒序遍歷數(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多多少分。

時間復雜度為，空間復雜度為，其中n是石頭的數(shù)量。

計算dp數(shù)組的過程需要遍歷所有的狀態(tài)，其中每個狀態(tài)需要O(1)的時間進行計算，因此總時間復雜度為。另外，由于需要維護一個二維數(shù)組，所以需要的額外空間來存儲這些狀態(tài)。

三種算法總結(jié)

綜上所述，第二種和第三種方法的時間復雜度和空間復雜度相同，都比第一種方法更加高效。在實際使用中，我們應該優(yōu)先選擇動態(tài)規(guī)劃算法來解決這類問題，因為它能夠在多項式時間內(nèi)求解，而遞歸算法則往往會導致指數(shù)級別的復雜度。

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

// 時間復雜度和剛才講的一樣！
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))
}

[圖片上傳失敗...(image-1f0cac-1683641517987)]

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];

[圖片上傳失敗...(image-82d253-1683641517987)]

c完整代碼如下：

#include <stdio.h>
#include <stdlib.h>

int f(int* stones, int sum, int L, int R);
int s(int* stones, int sum, int L, int R);

int stoneGameVII1(int* stones, int stonesSize) {
    int sum = 0;
    for (int i = 0; i < stonesSize; i++) {
        sum += stones[i];
    }
    int alice = f(stones, sum, 0, stonesSize - 1);
    int bob = s(stones, sum, 0, stonesSize - 1);
    return abs(alice - bob);
}

// 先手
int f(int* stones, int sum, int L, int R) {
    if (L == R) { // 只能一塊兒了！
        return 0;
    }

    // L為起點
    int p1 = sum - stones[L] + s(stones, sum - stones[L], L + 1, R);
    int against1 = f(stones, sum - stones[L], L + 1, R);

    // R為終點
    int p2 = sum - stones[R] + s(stones, sum - stones[R], L, R - 1);
    int against2 = f(stones, sum - stones[R], L, R - 1);

    if (p1 - against1 > p2 - against2) {
        return p1;
    }
    return p2;
}

// 后手
int s(int* stones, int sum, int L, int R) {
    if (L == R) {
        return 0;
    }

    // 當前的是后手
    // 對手，先手！
    int against1 = sum - stones[L] + s(stones, sum - stones[L], L + 1, R);
    // 當前用戶的得分！后手！是對手決定的！
    int get1 = f(stones, sum - stones[L], L + 1, R);

    int against2 = sum - stones[R] + s(stones, sum - stones[R], L, R - 1);
    int get2 = f(stones, sum - stones[R], L, R - 1);

    if (against1 - get1 > against2 - get2) {
        return get1;
    }
    return get2;
}

int stoneGameVII2(int* stones, int stonesSize) {
    int N = stonesSize;
    int** dpf = (int**)malloc(N * sizeof(int*));
    int** dps = (int**)malloc(N * sizeof(int*));
    for (int i = 0; i < N; i++) {
        dpf[i] = (int*)malloc(N * sizeof(int));
        dps[i] = (int*)malloc(N * sizeof(int));
        memset(dpf[i], 0, N * sizeof(int));
        memset(dps[i], 0, N * sizeof(int));
    }
    int* presum = (int*)malloc((N + 1) * sizeof(int));
    memset(presum, 0, (N + 1) * sizeof(int));
    for (int i = 0; i < N; i++) {
        presum[i + 1] = presum[i] + stones[i];
    }
    for (int L = N - 2; L >= 0; L--) {
        for (int R = L + 1; R < N; R++) {
            int sumLR = presum[R + 1] - presum[L];
            int a = sumLR - stones[L] + dps[L + 1][R];
            int b = dpf[L + 1][R];
            int c = sumLR - stones[R] + dps[L][R - 1];
            int d = dpf[L][R - 1];
            dpf[L][R] = (a - b > c - d) ? a - b : c - d;
            dps[L][R] = (b > d) ? b : d;
        }
    }
    int result = abs(dpf[0][N - 1] - dps[0][N - 1]);
    for (int i = 0; i < N; i++) {
        free(dpf[i]);
        free(dps[i]);
    }
    free(presum);
    free(dpf);
    free(dps);
    return result;
}

int dp[1001];

int stoneGameVII3(int* stones, int stonesSize) {
    int n = stonesSize;
    memset(dp, 0, sizeof(dp));
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
            dp[i] = stones[i];
        }
    }
    int alicePick = n % 2 == 0 ? 1 : 0;
    for (int len = 2; len <= n; len++, alicePick = !alicePick) {
        for (int i = 0, j = len - 1; j < n; i++, j++) {
            if (alicePick) {
                dp[i] = dp[i] > dp[i + 1] ? dp[i] : dp[i + 1];
            }
            else {
                int a = dp[i] + stones[j];
                int b = stones[i] + dp[i + 1];
                dp[i] = a < b ? a : b;
            }
        }
    }
    return dp[0];
}

int main() {
    int stones[] = { 5, 3, 1, 4, 2 };
    int stonesSize = sizeof(stones) / sizeof(int);
    printf("stoneGameVII1: %d\n", stoneGameVII1(stones, stonesSize));
    printf("stoneGameVII2: %d\n", stoneGameVII2(stones, stonesSize));
    printf("stoneGameVII3: %d\n", stoneGameVII3(stones, stonesSize));
    return 0;
}

[圖片上傳失敗...(image-c3f18e-1683641517987)]

c++完整代碼如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int f(vector<int>& stones, int sum, int L, int R);
int s(vector<int>& stones, int sum, int L, int R);

int stoneGameVII1(vector<int>& stones) {
    int sum = 0;
    for (int num : stones) {
        sum += num;
    }
    int alice = f(stones, sum, 0, stones.size() - 1);
    int bob = s(stones, sum, 0, stones.size() - 1);
    return abs(alice - bob);
}

// 先手
int f(vector<int>& stones, int sum, int L, int R) {
    if (L == R) { // 只能一塊兒了！
        return 0;
    }

    // L為起點
    int p1 = sum - stones[L] + s(stones, sum - stones[L], L + 1, R);
    int against1 = f(stones, sum - stones[L], L + 1, R);

    // R為終點
    int p2 = sum - stones[R] + s(stones, sum - stones[R], L, R - 1);
    int against2 = f(stones, sum - stones[R], L, R - 1);

    if (p1 - against1 > p2 - against2) {
        return p1;
    }
    return p2;
}

// 后手！
int s(vector<int>& stones, int sum, int L, int R) {
    if (L == R) {
        return 0;
    }

    // 當前的是后手
    // 對手，先手！
    int against1 = sum - stones[L] + s(stones, sum - stones[L], L + 1, R);
    // 當前用戶的得分！后手！是對手決定的！
    int get1 = f(stones, sum - stones[L], L + 1, R);

    int against2 = sum - stones[R] + s(stones, sum - stones[R], L, R - 1);
    int get2 = f(stones, sum - stones[R], L, R - 1);

    if (against1 - get1 > against2 - get2) {
        return get1;
    }
    return get2;
}

// 動態(tài)規(guī)劃版
int stoneGameVII2(vector<int>& stones) {
    int N = stones.size();
    vector<vector<int>> dpf(N, vector<int>(N, 0));
    vector<vector<int>> dps(N, vector<int>(N, 0));
    vector<int> presum(N + 1, 0);
    for (int i = 0; i < N; i++) {
        presum[i + 1] = presum[i] + stones[i];
    }
    for (int L = N - 2; L >= 0; L--) {
        for (int R = L + 1; R < N; R++) {
            int sumLR = presum[R + 1] - presum[L];
            int a = sumLR - stones[L] + dps[L + 1][R];
            int b = dpf[L + 1][R];
            int c = sumLR - stones[R] + dps[L][R - 1];
            int d = dpf[L][R - 1];
            dpf[L][R] = max(a - b, c - d);
            dps[L][R] = max(b, 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é)算時機！這是這種嘗試的核心！
int dp[1001];

// 時間復雜度和剛才講的一樣！
int stoneGameVII3(vector<int>& s) {
    int n = s.size();
    memset(dp, 0, sizeof(dp));
    if (n % 2 == 0) {
        for (int i = 0; i < n; i++) {
            dp[i] = s[i];
        }
    }
    bool alicePick = n % 2 == 0;
    for (int len = 2; len <= n; len++, alicePick = !alicePick) {
        for (int i = 0, j = len - 1; j < n; i++, j++) {
            dp[i] = alicePick ? max(dp[i], dp[i + 1]) : min(dp[i] + s[j], s[i] + dp[i + 1]);
        }
    }
    return dp[0];
}

int main() {
    vector<int> stones = { 5, 3, 1, 4, 2 };
    cout << "stoneGameVII1: " << stoneGameVII1(stones) << endl;
    cout << "stoneGameVII2: " << stoneGameVII2(stones) << endl;
    cout << "stoneGameVII3: " << stoneGameVII3(stones) << endl;
    return 0;
}

[圖片上傳失敗...(image-f2f351-1683641517987)]