技术教程 编程教程 2023-05-09：石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。 有 n 块石子排成一排。 每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头， 并获得与该行中剩余石头值 正文

2023-05-09：石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。 有 n 块石子排成一排。 每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头， 并获得与该行中剩余石头值

2023-06-20,,

2023-05-09：石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。

每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，

并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），

所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，

如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

输入：stones = [5,3,1,4,2] 。

输出：6 。

答案2023-05-09：

该问题的解法有多种，下面分别对三个函数的实现过程进行详细描述。

1.递归版

该函数使用递归实现了石子游戏。首先计算出整个石子数组的和sum，然后调用f函数获取Alice获得的最大得分，再调用s函数获取Bob获得的最大得分，最终计算出差值并返回。

f函数表示当前轮到Alice操作，从L位置取走一个石头或从R位置取走一个石头的情况下，Alice能获得的最大得分。将这两种情况所获得的得分与对手（Bob）相比较，选择更优的方案。其中，对手的得分由s函数计算。

s函数表示当前轮到Bob操作，在剩余石子中选择一个最优的石子让Alice取走，并计算自己的得分。此处需要注意，当前是Bob在操作，但是得分却是Alice决定的，因为Alice可以在自己的回合中选择拿走哪一块石头，进而影响Bob的得分。

时间复杂度为$O(2^n)$，空间复杂度为$O(n)$，其中n是石头的数量。

因为在每一层递归中，都会有两种分支需要继续递归下去，所以总共会有2^n个叶子节点。另外，由于递归的深度最多为n层，所以需要O(n)的栈空间来存储每一层递归的状态。

2.动态规划版

该函数使用动态规划实现了石子游戏。首先计算出整个石子数组的前缀和presum，然后定义两个二维数组dpf和dps。其中，dpf[i][j]表示当只剩下第i到第j块石头时，先手（即Alice）能够获得的最大得分；dps[i][j]表示当只剩下第i到第j块石头时，后手（即Bob）能够获得的最大得分。

接着，从右下角开始倒序遍历数组，计算出dpf和dps数组的值。具体计算方法如下：

当前轮到先手操作，先手可以选择拿走第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块石头中能够获得的最大得分。因为是先手行动，所以先手最终能够获得的得分为这两种情况中的较大值。
当前轮到后手操作，后手只能在剩余的石头中选择一个最优的石头让先手取走，并计算自己的得分。即后手能够获得的最大得分为sumLR - stones[i] + dps[L+1][R]或sumLR - stones[j] + dps[L][R-1]中的较大值。

最终，返回dpf[0][n-1] - dps[0][n-1]的绝对值，即Alice和Bob得分的差值。

时间复杂度为$O(n2)$，空间复杂度为$O(n2)$，其中n是石头的数量。

计算dpf和dps数组的过程需要遍历所有的状态，其中每个状态需要O(1)的时间进行计算，因此总时间复杂度为$O(n2)$。另外，因为需要维护两个二维数组，所以需要O(n2)的额外空间来存储这些状态。

3.另一种尝试

该函数使用动态规划实现了石子游戏。定义dp[len][i]表示从第i块石头出发，当长度为len时，Alice能比Bob多多少分？其中所谓的长度为len是指剩下的石头数量。例如，假设当前还剩下5块石头，即len=5，则dp[5][i]表示从第i块石头出发，当只剩下5块石头时，Alice能比Bob多多少分。

首先，如果剩余的石头数量为偶数，那么Alice一定会选择先手，并且每次都取走价值最高的石头。因此，对于所有的i，dp[1][i]都等于stones[i]。对于剩余的情况，我们需要使用动态规划来计算dp[len][i]。具体来说，我们可以考虑当前轮到先手操作，他可以选择拿走第i块石头或第j块石头，然后根据后续状态递归计算。

因为状态之间存在依赖关系，所以我们可以倒序遍历数组，从右下角开始计算。具体来说，我们可以按照如下方式进行状态转移：

如果当前是先手操作，那么他可以选择拿走第i块石头或第j块石头。如果他选择了第i块石头，那么剩下的石头数量就变成了len-1，并且下一个人变成了后手，此时当前状态的价值为stones[i]-dp[len-1][i+1]；如果他选择了第j块石头，那么剩下的石头数量也变成了len-1，但是下一个人仍然是后手，此时当前状态的价值为stones[j]-dp[len-1][i]。因为是先手行动，所以他会选择让自己的得分更高，即dp[len][i]=max(stones[i]-dp[len-1][i+1], stones[j]-dp[len-1][i])。
如果当前是后手操作，那么他只能在剩余的石头中选择一个最优的石头让先手取走，并计算自己的得分。具体来说，如果他选择了第i块石头，那么剩余的石头数量就变成了len-1，并且下一个人变成了先手，此时当前状态的价值为-dp[len-1][i+1]；如果他选择了第j块石头，那么剩余的石头数量也变成了len-1，但是下一个人仍然是先手，此时当前状态的价值为-dp[len-1][i]。因为是后手行动，所以他会选择让自己的得分更高，即dp[len][i]=min(-dp[len-1][i+1], -dp[len-1][i])。

最终，我们返回dp[0][n-1]的值，即从第0块石头出发，当长度为n时，Alice能比Bob多多少分。

时间复杂度为$O(n2)$，空间复杂度为$O(n2)$，其中n是石头的数量。

计算dp数组的过程需要遍历所有的状态，其中每个状态需要O(1)的时间进行计算，因此总时间复杂度为$O(n2)$。另外，由于需要维护一个二维数组，所以需要$O(n2)$的额外空间来存储这些状态。

三种算法总结

综上所述，第二种和第三种方法的时间复杂度和空间复杂度相同，都比第一种方法更加高效。在实际使用中，我们应该优先选择动态规划算法来解决这类问题，因为它能够在多项式时间内求解，而递归算法则往往会导致指数级别的复杂度。

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

}

// 动态规划版

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动态规划表 + 空间压缩 + 尽量优化

// dp[len][i] : 从i出发，当长度为len的情况下，Alice能比Bob多多少分？

// 要注意结算时机！这是这种尝试的核心！

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))

}

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

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;

}

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;

}

// 动态规划版

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动态规划表 + 空间压缩 + 尽量优化

// dp[len][i] : 从i出发，当长度为len的情况下，Alice能比Bob多多少分？

// 要注意结算时机！这是这种尝试的核心！

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;

}

2023-05-09：石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。 有 n 块石子排成一排。 每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头， 并获得与该行中剩余石头值的相关教程结束。

《2023-05-09：石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。 有 n 块石子排成一排。 每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头， 并获得与该行中剩余石头值.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!