Leetcode每日一题 —— 1872. 石子游戏 VIII

看不懂，已经不属于我能去理解得地步了

抱歉 ^-^

可能是因为我写的太乱了，怎么说呢，感觉我说不清想表达的意思。

完蛋了，我已经彻底遗忘古法编程了

python这么写也很慢 不知道怎么压缩了 ^-^

class Solution:

    def stoneGameVIII(self, stones: List[int]) -> int:     

        f = s = sum(stones)

        # dp[i]: 从下标[i: n - 1]中选择下标i的最大值

        # 选i: +pre[i], -dp[i+1]

        # 不选i: dp[i+1]

        for i in range(len(stones) - 2, 0, -1):

            s -= stones[i + 1]

            if s - f > f:

                f = s - f



        return f

看了提示才写出来，好像是比较典型的零和博弈 dp，在石子系列前几道题中某一道出现过。

class Solution {

public:

    int stoneGameVIII(vector<int>& stones) {

        // 有点前缀和的意思，每次选择石头其实就在算前缀和

        int n=stones.size();

        // 先计算前缀和

        vector<int> pre(n+1,0);

        for(int i=1;i<=n;i++){

            pre[i]=pre[i-1]+stones[i-1];

        }

        // 定义 dp[i] 为当前玩家从 i 开始最多能领先对手多少分

        vector<int> dp(n+1,0);

        // 如果选择合并前 t 个石头，那么当前玩家新增的分数就是 pre[t]

        // 后一个玩家也是从 t 开始的，因此 dp[t] 表示后一个玩家领先当前玩家多少，因此要减去 dp[t]

        // 因此有 dp[i] = max(pre[t]-dp[t]) 对于所有的 t>i

        // 这个 dp 显然是倒着推的

        // 因为 dp[i+1] 已经计算了 max(pre[t']-dp[t']) 对于所有的 t'>i+1

        // 因此可以简化成 O(n) 级别的 dp[i] = max(dp[i+1], pre[i+1]-dp[i+1])

        dp[n]=0; // 没石头了

        dp[n-1]=pre[n]; // 这样写是以防 pre[n] < 0，后面从 i=n-2 开始倒推

        for(int i=n-2;i>=0;i--){

            dp[i]=max(dp[i+1], pre[i+1]-dp[i+1]);

        }

        // Alice 先手，dp[1] 就是 Alice 和 Bob 的最大分差

        return dp[1];

    }

};

dfs(i)表示的最早刻度在i时的净胜分

class Solution:

    def stoneGameVIII(self, stones: List[int]) -> int:

        n = len(stones)

        s = list(accumulate(stones, initial=0))

        @cache

        def dfs(i: int) -> int:

            if i == n - 1:

                return s[-1]

            return max(dfs(i + 1), s[i + 1] - dfs(i + 1))

        return dfs(1)

看见hard就不想写

class Solution:

    def sortColors(self, nums: List[int]) -> None:

        """

        Do not return anything, modify nums in-place instead.

        """

        n = len(nums)

        l, r = 0, n-1

        i = 0

        while i <= r:

            if nums[i] == 2:

                nums[r], nums[i] = nums[i], nums[r]

                r -= 1

            elif nums[i] == 0:

                nums[l], nums[i] = nums[i], nums[l]

                l += 1

                i += 1

            else:

                i += 1

"""

2 0 1

1 0 2

0 1 2



"""

impl Solution {

    pub fn stone_game_viii(mut stones: Vec<i32>) -> i32 {

        let n = stones.len();



        for i in 1..n {

            stones[i] += stones[i - 1];

        }



        let mut dp = stones[n - 1];



        for i in (1..n - 1).rev() {

            dp = dp.max(stones[i] - dp);

        }



        dp

    }

}

和GPT交流了一下才做出来

class Solution:

    def stoneGameVIII(self, stones: List[int]) -> int:

        prefix=[]

        sum=0

        for i in stones:

            sum+=i

            prefix.append(sum)

        dp=prefix[-1]

        for i in range(len(stones)-2,0,-1):

            dp=max(dp,prefix[i]-dp)

        return dp