LC 1388. 3n 块披萨

https://leetcode-cn.com/problems/pizza-with-3n-slices/

这种选择规则的最终结果就是，你的选择必须满足条件不能选择相邻的两块，除此之外可以自由选择。如果是这样的话，那就可以简化成为简单的dp问题了。不过考虑头尾属于相邻的情况，需要分别考虑 a)不取头 b)不取尾两种情况。

这个dp问题是dp[i][j]表示在前面i块pizza中取了j块的价值, dp[i][j] = max of

dp[i-1][j]
dp[i-2][j-1] + slices[i]

为了节省空间的话可以使用3个滚动数组分别表示dp[i],dp[i-1],dp[i-2].

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        def calc(xs):
            n = len(xs)
            t = (n + 1) // 3
            dp = [[0] * (t + 1) for _ in range(n + 1)]
            for i in range(1, n + 1):
                for j in range(1, t + 1):
                    dp[i][j] = max(dp[i - 1][j], (dp[i - 2][j - 1] if i >= 2 else 0) + xs[i - 1])
            return dp[n][t]

        ans0 = calc(slices[:-1])
        ans1 = calc(slices[1:])
        ans = max(ans0, ans1)
        return ans