以下是核心DP逻辑的详细分析:
dp[l][r] = Math.max(a[l] - dp[l +1][r], a[r] - dp[l][r - 1]): 这行代码是整个动态规划的心脏。它计算当前玩家在序列的某个区间[l, r]内能获得的最大分数差。玩家可以选择序列左端的数字a[l]或者右端的数字a[r],取决于这两种选择之后对手在剩余序列上的最优策略(由dp[l+1][r]和dp[l][r-1]表示)。因为这里涉及减去对手的得分,实际上是在计算分数差。
注意,动态规划的填表顺序是按照区间的长度来的,从1开始到n结束。这是因为在计算dp[l][r]时,我们需要先知道更小区间的dp值,这就是为什么我们先从长度更小的区间开始计算的原因,即遵循了动态规划中的“自底向上”的原则。
最后,我们利用sum(序列中所有数的总和)和dp[1][n](序列从第一个到最后一个数字时,玩家一与玩家二的最大分数差)来计算两个玩家的最终得分。
import java.util.*;
public class Main{
static final int N = 110; // 定义序列的最大长度。
static int[] a = new int[N]; // 存储序列的数组。
static int[][] dp = new int[N][N];
// 动态规划数组,dp[i][j]表示当序列从第i到第j时,当前玩家能获得的最大分数。
public static void main(String[] args) {
Scanner sca = new Scanner(System.in);
int n = sca.nextInt();
int sum = 0; // 总分数。
for (int i = 1; i <= n; i++ ) // 循环读取序列中的数字。
{
a[i] = sca.nextInt(); // 存储每个数字。
sum += a[i]; // 累加总分数。
}
for (int len = 1; len <= n; len++ ) // 从长度为1的序列开始,逐渐增加长度。
{
for (int l = 1; l + len - 1 <= n; l++ ) // 枚举每个可能的序列起点。
{
int r = l + len - 1; // 序列终点。
// dp[l][r]是玩家从l到r能获得的最大分数,它是以下两种情况的较大值:
// 1. 玩家选择左端点,得分为a[l],减去在剩余序列中对手能得到的最大分数。
// 2. 玩家选择右端点,得分为a[r],减去在剩余序列中对手能得到的最大分数。
dp[l][r] = Math.max(a[l] - dp[l +1][r], a[r] - dp[l][r - 1]);
}
}
int firstPlayerScore = (sum + dp[1][n]) / 2;
// 根据dp数组的最后结果计算玩家一的分数。
int secondPlayerScore = (sum - dp[1][n]) / 2;
// 玩家二的分数为总分减去玩家一的分数。
System.out.println(firstPlayerScore + " " + secondPlayerScore);
}
}