[数据结构与算法]1388. 3n 块披萨 动态规划

1388. 3n 块披萨

难度困难104

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

• 你挑选?任意?一块披萨。
• Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
• Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
• 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组?slices?表示。

请你返回你可以获得的披萨大小总和的最大值。

示例 1：

输入：slices = [1,2,3,4,5,6]
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

示例 2：

输入：slices = [8,9,8,6,1,1]
输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

提示：

• 1 <= slices.length <= 500
• slices.length % 3 == 0
• 1 <= slices[i] <= 1000

N

失败了，看了才会。。。已经想到去掉首尾算两次，但是 x 里面选 y 不记得怎么写了T T。完全按 打家劫舍II 来算的话，一共6块，选 1 3 5 是不行的, 只能选 2 块。

方法：动态规划

1. 因为环形，头尾不能同时选，去掉头尾各算一遍
2. 和 打家劫舍II 不同的是，有选择数量的限制，需要多算一层数量。当前可以从数量-1的位置加上当前的，或者直接选前面数量一样的
3. 对于第一块的情况，选几个都是自身

class Solution {
    public int maxSizeSlices(int[] slices) {
        int n = slices.length;
        return Math.max(find(slices,0,n-1),find(slices,1,n));
    }

    private int find(int[] slices, int start, int end){
        int n = slices.length;
        int v = n/3;
        int[][] dp = new int[n][v+1];
        for(int i = start; i < end; i++){
            for(int j = 1; j <= v; j++){
                dp[i][j] =  Math.max(i==0?0:dp[i-1][j],slices[i]+(i>=2?dp[i-2][j-1]:0));
            }
        }

        return Math.max(dp[n-1][v],dp[n-2][v]);
    }
}

时间复杂度：O(n^2)
空间复杂度：O(n^2)