1388.3n pizza dynamic planning

1388. 3n A piece of pizza

Difficulty 104

Here is a pizza for you , It consists of 3n Blocks are made up of parts of different sizes , Now you and your friends need to divide pizza according to the following rules ：

• You choose   arbitrarily   A piece of pizza .
• Alice You will choose the next pizza in the counterclockwise direction of the pizza you choose .
• Bob You will choose the pizza you choose, and the next pizza will be clockwise .
• Repeat the above process until there is no pizza left .

The size of each pizza is determined by a circular array in a clockwise direction  slices  Express .

Please return the maximum total pizza size you can get .

Example 1：

 Input ：slices = [1,2,3,4,5,6]
 Output ：10
 explain ： Select a size of  4  Of pizza ,Alice  and  Bob  Choose the size of  3  and  5  Of pizza . Then you choose the size  6  Of pizza ,Alice  and  Bob  Choose the size of  2  and  1  Of pizza . The total size of pizza you get is  4 + 6 = 10 .

Example 2：

 Input ：slices = [8,9,8,6,1,1]
 Output ：16
 explain ： The size of both rounds is  8  Of pizza . If you choose the size  9  Of pizza , Your friends will choose the size  8  Of pizza , In this case, your total is not the largest .

Tips ：

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

N

failed , Only after watching it ... I've thought of removing the head and tail twice , however x Choose from y I don't remember how to write T T. Press completely raid homes and plunder houses II If it comes to calculation , altogether 6 block , choose 1 3 5 You can't , Only choose 2 block .

Method ： Dynamic programming

1. Because the ring , You can't choose both ends , Take out the head and tail and calculate them once
2. and raid homes and plunder houses II The difference is , There is a limit on the number of choices , You need to count one more layer . At present, we can start from quantity -1 Add the current , Or directly choose the same number as the previous
3. For the first block , Choose a few are their own

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]);
    }
}

Time complexity ：O(n^2)
Spatial complexity ：O(n^2)