2023-07-05：爱丽丝和鲍勃继续他们的石子游戏

许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]

游戏以谁手中的石子最多来决出胜负。

爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M

然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设爱丽丝和鲍勃都发挥出最佳水平W

返回爱丽丝可以得到的最大数量的石头。

输入：piles = [2,7,9,4,4]。

输出：10。

答案2023-07-05：

1.算法 stoneGameII1：暴力方法

• • 首先定义函数 stoneGameII1，接收一个石子堆的切片 piles 作为参数，并返回爱丽丝可以得到的最大数量的石头。

• • 在函数 stoneGameII1 中调用函数 first1，并传入初始参数 piles、index=0（表示当前石子堆的索引）、m=1（表示当前的 M 值）。

• • 函数 first1 的作用是计算爱丽丝在当前石子堆的状态下的最优解。如果当前石子堆的索引达到了最后一个位置（即 index == len(piles)），则返回 0（石子已经全部取完）。

• • 否则，初始化变量 best = 0（当前的最优解）和 pre = 0（当前已经取走的石子数量）。

• • 开始一个循环，从当前索引开始遍历石子堆（i = index），并且用变量 j 记录当前取走的石子堆的数量（初始值为 1）。

• • 在循环中，更新变量 pre = pre + piles[i]，即计算当前的已取走的石子数量。

• • 然后，根据当前的石子堆状态以及剩余可取的石子堆的数量（int(math.Max(float64(j), float64(m)))），调用函数 second1，并传入相应的参数，计算爱丽丝在下一轮的最优解。

• • 更新变量 best = int(math.Max(float64(best), float64(pre+second1(piles, i+1, int(math.Max(float64(j), float64(m)))))))，即取当前轮最优解和已取走的石子数量之和的较大值作为当前的最优解。

• • 循环结束后，返回变量 best。

函数 second1 的作用是计算鲍勃在当前石子堆的状态下的最优解，其过程与函数 first1 类似。

• • 首先判断是否遍历到了最后一个石子堆，如果是，则返回 0（石子已全部取走）。

• • 否则，初始化变量 worse = math.MaxInt64（当前的最差解）。

• • 开始一个循环，从当前索引开始遍历石子堆，并用变量 j 记录当前取走的石子堆的数量（初始值为 1）。

• • 在循环中，更新变量 worse = int(math.Min(float64(worse), float64(first1(piles, i+1, int(math.Max(float64(j), float64(m)))))))，即取当前轮最差解和已取走的石子数量之和的较小值作为当前的最差解。

• • 循环结束后，返回变量 worse。

2.算法 stoneGameII2：记忆化搜索

• • 首先定义函数 stoneGameII2，接收一个石子堆的切片 piles 作为参数，并返回爱丽丝可以得到的最大数量的石头。

• • 在函数 stoneGameII2 中，首先初始化变量 n 为石子堆的数量，创建两个二维切片 f 和 s，用于存储记忆化搜索的结果。

• • 利用循环，初始化 f 和 s 的值为 -1。

• • 调用函数 first2，并传入初始参数 piles、index=0（表示当前石子堆的索引）、m=1（表示当前的 M 值）、f 和 s。

• • 函数 first2 的作用是计算爱丽丝在当前石子堆的状态下的最优解，其过程类似函数 first1，但加入了记忆化搜索的机制。

• • 首先判断是否已经计算过该状态的结果，如果是，则直接返回存储的结果 f[index][m]。

• • 否则，继续计算最优解。

• • 在计算过程中，每一轮的最优解都会存储在 f[index][m]，以避免重复计算。

• • 在循环中，需要调用函数 second2，传入相应的参数，计算鲍勃在当前石子堆的状态下的最优解，并存储在 s[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))] 中。

• • 循环结束后，将最优解保存到 f[index][m] 中，并返回最优解。

函数 second2 的作用是计算鲍勃在当前石子堆的状态下的最优解，与函数 second1 类似，但加入了记忆化搜索的机制。

• • 首先判断是否已经计算过该状态的结果，如果是，则直接返回存储的结果 s[index][m]。

• • 否则，继续计算最优解。

• • 在计算过程中，每一轮的最优解都会存储在 s[index][m]，以避免重复计算。

• • 循环结束后，将最优解保存到 s[index][m] 中，并返回最优解。

3.算法 stoneGameII3：严格位置依赖的动态规划，一张表的版本

• • 首先定义函数 stoneGameII3，接收一个石子堆的切片 piles 作为参数，并返回爱丽丝可以得到的最大数量的石头。

• • 在函数 stoneGameII3 中，首先初始化变量 n 为石子堆的数量，创建两个二维切片 f 和 s，表示爱丽丝和鲍勃在每个石子堆的状态下的最优解。

• • 利用循环，初始化 f 和 s 的值为 0。

• • 初始化变量 sum = 0，用于记录累计的石子数。

• • 从最后一个石子堆开始循环，更新变量 sum = sum + piles[index]，即计算当前的累计石子数。

• • 在循环中，根据动态规划的思想，计算爱丽丝和鲍勃的最优解。

• • 首先计算爱丽丝在当前石子堆状态下的最优解。

• • 声明变量 best = 0，表示当前的最优解。

• • 声明变量 pre = 0，表示当前已经取走的石子数量。

• • 在循环中，用变量 j 记录当前取走的石子堆的数量（初始值为 1）。

• • 在循环中，更新变量 pre = pre + piles[i]，即计算当前的已取走的石子数量。

• • 根据当前的石子堆状态以及剩余可取的石子堆的数量（int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m))))）），计算爱丽丝在下一轮的最优解 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)))))])))，取当前轮最优解和已取走的石子数量之和的较大值作为当前的最优解。

• • 计算鲍勃在当前石子堆状态下的最优解。

• • 声明变量 worse = math.MaxInt64，表示当前的最差解。

• • 在循环中，用变量 j 记录当前取走的石子堆的数量（初始值为 1）。

• • 在循环中，更新变量 worse = int(math.Min(float64(worse), float64(f[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))])))，取当前轮最差解和已取走的石子数量之和的较小值作为当前的最差解。

• • 循环结束后，更新 f[index][m] = best 和 s[index][m] = worse。

• • 返回 f[0][1]，即爱丽丝在初始状态下的最优解。

4.算法 stoneGameII4：严格位置依赖的动态规划

• • 首先定义函数 stoneGameII4，接收一个石子堆的切片 piles 作为参数，并返回爱丽丝可以得到的最大数量的石头。

• • 在函数 stoneGameII4 中，首先初始化变量 n 为石子堆的数量，创建一个二维切片 dp，用于存储动态规划的结果。

• • 利用循环，初始化 dp 的值为 0。

• • 初始化变量 sum = 0，用于记录累计的石子数。

• • 从最后一个石子堆开始循环，更新变量 sum = sum + piles[i]，即计算当前的累计石子数。

• • 在循环中，根据动态规划的思想，计算爱丽丝的最优。

stoneGameII1的时间复杂度为$O(2^n)$，空间复杂度为$O(n)$。

stoneGameII2的时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$。

stoneGameII3的时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$。

stoneGameII4的时间复杂度为$O(n^2)$，空间复杂度为$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
}

// 严格位置依赖的动态规划，一张表的版本
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]
}

// 严格位置依赖的动态规划
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))
}