2024.2.3力扣每日一题——石子游戏7

题目来源

力扣每日一题；题序：1690

我的题解

方法一 前缀和+记忆化搜索

假设需要的区间为[i,j]的石头待选择，对于本轮的玩家来说，可以选择最左侧的元素i和最右侧的元素j。假设剩下的元素为[$s_i,s_{i+1},...,s_j$]，并且该轮轮到Bob选择，Bob有两种选择：

• 假设选择$s_i$，则其得很为${\sum }_{k-i+1}^j$，剩下的元素为[$s_{i+1},s_{i+2},...,s_j$]，由于Alice乡努力扩大得分差值，假设Alice在剩余石头序列中的得分与Bob得分最大差值为$f(i+1,j)$，则此时Bob与Alice的得分差值为${\sum }_{k-i+1}^j-f(i+1,j)$
• 假设选择$s_j$，则其得很为${\sum }_{k-i}^{j-1}$，剩下的元素为[$s_i,s_{i+1},...,s_{j-1}$]，由于Alice乡努力扩大得分差值，假设Alice在剩余石头序列中的得分与Bob得分最大差值为$f(i,j-1)$，则此时Bob与Alice的得分差值为${\sum }_{k-i}^{j-1}-f(i,j-1)$
• 在序列[$s_i,s_{i+1},...,s_j$]中，Bob与Alice得分差值的最大值为$f(i,j)=max({\sum }_{k-i+1}^j-f(i+1,j),{\sum }_{k-i}^{j-1}-f(i,j-1))$。所以，最大得分差值=当前玩家所获得的价值-剩余序列中对手与自己的得分差值的最大值。

可以采用自顶向下的记忆化搜索，要求区间[i,j]得分的最大差值为$f(i,j)$，只需要求出区间[i,j-1]和[i+1,j]的最优值即可。

时间复杂度：O($n^2$)。其中，n表示数组的长度。需要分别求每个区间（i,j）的最优子状态，一共就有$n^2$个子状态需要计算。
空间复杂度：O($n^2$)。记忆化搜索的字典需要的空间。

public int stoneGameVII(int[] stones) {
    int n=stones.length;
    int[] preSum=new int[n+1];
    for(int i=0;i<n;i++){
        preSum[i+1]=preSum[i]+stones[i];
    }
    int[][] memo=new int[n][n];
    int left=0,right=n-1;
    return dfs(left,right,preSum,memo);
}
public int dfs(int left,int right,int[] sum,int[][] memo){
    if(left>=right){
        return 0;
    }
    if(memo[left][right]!=0){
        return memo[left][right];
    }
    // 取左边
    int res=Math.max(sum[right+1]-sum[left+1]-dfs(left+1,right,sum,memo),
    // 取右边
            sum[right]-sum[left]-dfs(left,right-1,sum,memo));
    memo[left][right]=res;
    return res;
}

方法二 前缀和+动态规划

也可以使用动态规划的思想来实现。可以先求区间[i,j]得分的最大差值，然后再求区间[i,j-1]和[i+1,j]的最优值，最后得出区间[0,n-1]的最大差值。
转移公式：dp[i][j]=max(sum[j+1]-sum[i+1]-dp[i+1][j],sum[j]-sum[i]-dp[i][j-1])

时间复杂度：O($n^2$)。其中，n表示数组的长度。需要分别求每个区间（i,j）的最优子状态，一共就有$n^2$个子状态需要计算。
空间复杂度：O($n^2$)。动态表需要的空间。

public int stoneGameVII(int[] stones) {
    int n=stones.length;
    int[] preSum=new int[n+1];
    for(int i=0;i<n;i++){
        preSum[i+1]=preSum[i]+stones[i];
    }
    int[][] dp=new int[n][n];
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<n;j++){
        //preSum[j+1]-preSum[i+1]表示[i+1,j]的和，preSum[j]-preSum[i]表示[i,j-1]的和
            dp[i][j]=Math.max(preSum[j+1]-preSum[i+1]-dp[i+1][j],preSum[j]-preSum[i]-dp[i][j-1]);
        }
    }
        return dp[0][n-1];
    }

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~