1563. Stone Game V

题目信息

题号:

1563

难度:

Hard

主题:

区间动态规划、博弈过程、前缀和

原题:

LeetCode 1563

重点:

每轮把当前数组切成两个非空部分,Bob 丢弃和较大的部分;和相等时 Alice 可选择保留哪一边,累计被保留部分的和

题目重述

给定正整数数组 stoneValue。Alice 每轮把当前数组切成左右两个非空连续部分。Bob 比较两部分元素和并丢弃和较大的部分;若两边相等,Alice 决定丢弃哪一边。Alice 得到保留下来部分的元素和作为本轮分数,并继续对该部分操作。

当剩余数组只有一个元素时游戏结束。请返回 Alice 能获得的最大总分。

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

自建示例

和相等时选择更有利的部分继续游戏:

输入:stoneValue = [1,2,3]
输出:4
解释:先切成 [1,2] 与 [3],两边和都为 3;保留 [1,2] 得 3 分,再得 1 分。

单元素数组无法切分:

输入:stoneValue = [5]
输出:0
解释:游戏立即结束,没有任何得分轮次。