题目链接
/**
* 思路：动态规划
* 用F[l][r]表示先选的人能拿到的最高分
* 用S[l][r]来表示后选的人能拿到的最高分
* 对于先选者，有两种选法
* 若先选者选A[0],则对于后面的1, ... ,n-1 数组，他就变成了后选者，此时能拿到的分为A[0]+S[1][n-1]
* 若先选者选A[n-1],则对于前面的数组0，...，n-2,同样变为后选者，此时能拿到得分为A[n-1]+S[0][n-2];
* 所以 F[0][n-1] = max(A[0]+S[1][n - 1],A[n - 1]+S[0][n - 2])
* 对于后选者，他能能到的最高分是受先选者控制的，即他只能选到先选者留给他的最小值，将其转化为数学形式就是
* S[l][r] = min(F[l + 1][r], F[l][r - 1])，因为先选者很聪明，肯定会把最低的分数留给他
*/
import java.util.Scanner;
public class MaxScore {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = scanner.nextInt();
}
System.out.println(findMaxScore(array, n));
scanner.close();
}
public static int findMaxScore(int[] A, int n) {
int[][] F = new int [n][n];
int[][] S = new int [n][n];
for (int r = 0; r < n; r++) {
F[r][r] = A[r];
S[r][r] = 0;
for (int l = r - 1; l >= 0; l--) {
F[l][r] = Math.max(A[l] + S[l + 1][r], A[r] + S[l][r - 1]);
S[l][r] = Math.min(F[l + 1][r], F[l][r - 1]);
}
}
return Math.max(F[0][n - 1], S[0][n - 1]);
}
}# 第四题
# 之前做过石子游戏问题，跟这道题基本相同，动态规划思路如下：
"""
我们可以创建一个二维数组 dp，其中 dp[i][j] 表示玩家在面对剩余的格子区间 [i, j] 时，能够获得的最大分数差值（玩家A的得分减去玩家B的得分）
状态方程分两种情况：
如果玩家选择左端点（格子 i），那么他会获得格子 i 上的分数 nums[i]，然后将剩余的格子区间变成 [i+1, j]，交给对手。所以，得分差值为 nums[i] - dp[i+1][j]。
如果玩家选择右端点（格子 j），那么他会获得格子 j 上的分数 nums[j]，然后将剩余的格子区间变成 [i, j-1]，交给对手。所以，得分差值为 nums[j] - dp[i][j-1]。
玩家会选择让得分差值最大化的那一种情况。所以 dp[i][j] 取两种情况中的较大值，这样玩家就能采用最优策略来最大化自己的得分。
我们在外层定义的循环用于遍历选取的子序列的长度，循环内部的I和J用于指代两端
"""
def stoneGame(nums):
n = len(nums)
# 创建一个二维数组dp，dp[i][j]表示从第i个石头到第j个石头之间的最大得分
dp = [[0] * n for _ in range(n)]
# 初始化dp数组，单个石头的得分就是它自己的分数
for i in range(n):
dp[i][i] = nums[i]
# 动态规划计算dp数组
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
# 最终dp[0][n-1]表示玩家A和玩家B的得分差值
# 计算两名玩家的最终得分
total_score_a = (sum(nums) + dp[0][n - 1]) // 2
total_score_b = sum(nums) - total_score_a
# 输出得分较高的玩家的得分
return max(total_score_a, total_score_b)
n = int(input())
s = input().split(" ")
nums = [int(x) for x in s]
print(stoneGame(nums=nums))
##动态规划 五部曲
1、确定dp数组（dp table）以及下标的含义
dp[i][j]表示在i到j范围进行选择，A得分比B得分多多少（这个值可能时分数）
2、确定递推公式
dp[i][j]=max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])
3、dp数组如何初始化
当i=j时,dp[i][j]=nums[i],只要一个格子可以选，A先选，比B多nums[i]分
4、确定遍历顺序
我们初始化时，可以选的格子为一个，那我们的外层for循环就是从可选格子长度从2到n，内部循环就是遍历i可以取的值（保证j不会大于n-1）;
j=i+可选格子长度-1。
5、举例推导dp数组
dp[0][n-1]就是可选格子为n时A得分-B得分的值，分别算出A，B的值，取最大返回
package main
import "fmt"
func main() {
var n int
fmt.Scan(&n)
nums := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&nums[i])
}
res := stoneGame(nums)
fmt.Println(res)
}
func stoneGame(nums []int) int {
n := len(nums)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
sum := 0
for i := range dp {
sum += nums[i]
dp[i][i] = nums[i]
}
for length := 2; length < n+1; length++ {
for i := 0; i < n-length+1; i++ {
j := i + length - 1
dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])
}
}
totalA := (sum + dp[0][n-1]) / 2
totalB := sum - totalA
return max(totalA, totalB)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
#include <stdio.h>
#include <stdlib.h>
int findMaxScore(int* A, int n) {
// 创建二维数组 F 和 S
int** F = (int**)malloc(n * sizeof(int*));
int** S = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
F[i] = (int*)malloc(n * sizeof(int));
S[i] = (int*)malloc(n * sizeof(int));
}
// 动态规划求解最大分数
for (int r = 0; r < n; r++) {
// 初始化对角线上的值
F[r][r] = A[r];
S[r][r] = 0;
// 从右下角开始逐步往左上角计算
for (int l = r - 1; l >= 0; l--) {
// 先选者的最高分取决于两种选择的较大值
F[l][r] = (A[l] + S[l + 1][r] > A[r] + S[l][r - 1]) ? A[l] + S[l + 1][r] : A[r] + S[l][r - 1];
// 后选者的最高分取决于先选者留给他的最小值
S[l][r] = (F[l + 1][r] < F[l][r - 1]) ? F[l + 1][r] : F[l][r - 1];
}
}
// 返回先选者和后选者中的最大值
int result = (F[0][n - 1] > S[0][n - 1]) ? F[0][n - 1] : S[0][n - 1];
// 释放动态分配的内存
for (int i = 0; i < n; i++) {
free(F[i]);
free(S[i]);
}
free(F);
free(S);
return result;
}
int main() {
int n;
scanf("%d", &n);
int* array = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
printf("%d\n", findMaxScore(array, n));
free(array);
return 0;
}