石子游戏 V

标签: 数组 数学 动态规划 博弈

难度: Hard

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。

示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：

输入：stoneValue = [4]
输出：0

提示：

  • 1 <= stoneValue.length <= 500
  • 1 <= stoneValue[i] <= 10^6

Submission

运行时间: 764 ms

内存: 55.6 MB

"""
定义状态s=(i,j)，表示剩余的棋子为stoneValue[i:j]
dp[s]表示Alice当前面临状态s时未来所能获得的最大分数
转移方程：
    def f(i,j,k):
        a = sum(stoneValue[i:k])
        b = sum(stoneValue[k:j])
        if a < b:
            return a + dp[i,k]
        elif a==b:
            return a + max(dp[i,k], dp[j,k])
        else:
            return b + dp[j,k]            

    dp[i,j] = max{f(i,j,k) for k in range(i+1,j)}
最简单状态下的值：
    dp[i,i+1] = 0
返回：
    dp[0,N]
"""
import numpy as np
class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        A = [0] 
        for v in stoneValue:
            A.append(v+A[-1]) #记录到第i个石头的和
        @cache
        def f(i,j,k):
            a = A[k] - A[i]
            b = A[j] - A[k]
            if a<b:
                return a + game(i,k)
            elif a==b:
                return a + max(game(i,k), game(k,j))
            else:
                return b + game(k,j)
        
        N = len(stoneValue)
        @cache
        def game(i,j): # i和j是数组索引i到j
            if j==i+1: #只剩一个返回0
                return 0
            else:
                reward_list = [(k,min(A[k]-A[i], A[j]-A[k])) for k in range(i+1,j)]
                reward_list.sort(key = lambda x: -x[1]) #记录分割的大小
                max_f = -1e8
                for k,r in reward_list:
                    if 2*r > max_f:
                        max_f = max(max_f, f(i,j,k))
                    else:
                        continue
            return max_f

        return game(0,N)

Explain

该题解采用了动态规划的思路，定义状态dp[i,j]表示在子数组stoneValue[i:j]中Alice可以获得的最大分数。首先使用前缀和数组A来优化区间和的计算，使得任意子数组的和可以在O(1)时间内得到。对于任何一个分割位置k，计算左右子数组的和，并基于这两个和更新Alice的最大可能分数。转移方程考虑了三种情况：左子数组和小于、等于、或大于右子数组和。使用记忆化递归（通过cache装饰器）避免重复计算相同状态，从而提高效率。在每个状态下，先计算所有可能的分数，并按分数排序，然后只考虑可能提高最大分的选项来进一步优化运算。这种方式称为剪枝，减少了不必要的递归调用。

时间复杂度: O(n^3)

空间复杂度: O(n^2)

import numpy as np
from functools import cache
from typing import List

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        A = [0] 
        for v in stoneValue:
            A.append(v+A[-1]) # 累积和数组，A[k]是stoneValue[:k]的和
        @cache
        def f(i,j,k):
            a = A[k] - A[i] # 左侧子数组的和
            b = A[j] - A[k] # 右侧子数组的和
            if a < b:
                return a + game(i,k) # 如果左侧子数组和较小，选择左侧
            elif a == b:
                return a + max(game(i,k), game(k,j)) # 如果相等，选择两者中的较大者
            else:
                return b + game(k,j) # 如果右侧子数组和较大，选择右侧
        
        N = len(stoneValue)
        @cache
        def game(i,j): # 动态规划的主函数
            if j == i+1: # 只剩一个元素时，返回0
                return 0
            reward_list = [(k,min(A[k]-A[i], A[j]-A[k])) for k in range(i+1,j)]
            reward_list.sort(key=lambda x: -x[1]) # 按可能的得分从高到低排序
            max_f = -1e8
            for k,r in reward_list:
                if 2*r > max_f: # 剪枝，只考虑更新最大分的分割
                    max_f = max(max_f, f(i,j,k))
                else:
                    continue
            return max_f
        
        return game(0,N)

Explore

在'石子游戏V'题目中，Alice的目标是最大化自己的分数，这取决于每次分割后子数组的石子总和。因为Alice的得分基于较小的子数组总和，所以比较左右子数组的和是必要的，以确定哪个子数组的和较小（因为Alice会选择这个子数组的石子总和作为自己的分数）。如果直接计算可能的最大分数而不进行比较，就无法正确模拟游戏规则中的这一策略，即总是基于较小的子数组和来增加分数。

在函数`game`中，`reward_list`包含每个可能的分割点及其对应的最小子数组和，这个最小值是Alice能从当前分割获得的分数。`reward_list`按这个可能得到的分数从高到低进行排序，这样做的目的是优先考虑那些可能给Alice带来更高分数的分割点。剪枝操作则是基于一个观察：一旦找到一个分割点使得分数未能超过当前已知的最大分数，则不再考虑更低分数的分割点，因为它们不可能提供更高的分数。这种方法减少了不必要的计算，提高了效率。

在左右子数组和相等的情况下，Alice有两个选择：左边或右边的子数组。因为这两个子数组的和相等，Alice的得分将是这个共同的和值加上两边继续游戏可能得到的最大分数。因此，为了最大化Alice的总分数，需要考虑两边继续游戏的最大值。这种策略在分割点左右子数组和相等时是必需的，因为忽略任一侧可能的最大值都可能导致Alice失去获得更高总分的机会。

使用前缀和数组A可以大大优化连续子数组和的计算，将其从O(n)降低到O(1)，这对于重复计算区间和的问题很有帮助。然而，这种方法的缺点包括额外的空间复杂度（需要存储整个前缀和数组），以及前缀和数组的初始构建时间（虽然是线性时间，但在非常大的输入上仍然显著）。此外，在更新或修改原始数组的情况下，前缀和数组需要被重新计算，这在动态或实时数据变更的场景中可能不是最有效的方案。