三、石子游戏 VII
石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值
输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 =
[5,3,1,4]。 - 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 =
[3,1,4]。 - 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 =
[1,4]。 - 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 =
[4]。 - 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 =
[]。
得分的差值 18 - 12 =6。
class Solution:
def stoneGameVII(self, stones: List[int]) -> int:
n = len(stones)
sum = [0] * (n + 1)
for i in range(n):
sum[i + 1] = sum[i] + stones[i]
def get(l, r):
return sum[r + 1] - sum[l]
@cache
def dp(l, r):
if l == r:
return 0
return max(get(l + 1, r) - dp(l + 1, r), get(l, r - 1) - dp(l, r - 1))
ans = dp(0, n - 1)
dp.cache_clear()
return ans
# copy
四、堆叠长方体的最大高度
给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。
返回 堆叠长方体 cuboids 可以得到的 最大高度
class Solution(object):
def maxHeight(self, cuboids):
new_cuboids = []
for x in cuboids:
new_cuboids.append(sorted(x))
cuboids = new_cuboids
n = len(cuboids)
cuboids.sort(key=lambda x: x[0]*x[1]*x[2])
dp = [0] * n
for i in range(n):
dp[i] = cuboids[i][2]
for j in range(i):
if cuboids[j][1]<=cuboids[i][1] and cuboids[j][2] <= cuboids[i][2] and cuboids[j][0] <= cuboids[i][0]:
dp[i]=max(dp[i],dp[j]+cuboids[i][2])
return max(dp)
# copy
# 像 dp 中最长上升子序列
