LeetCode_动态规划_困难_1388.3n 块披萨

末蓝、 2023-10-14 22:20 36阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

*  你挑选任意一块披萨。
 *  Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
 *  Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
 *  重复上述过程直到没有披萨剩下。
 *  每一块披萨的大小按顺时针方向由循环数组 slices 表示。

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

**示例 1：**  
![在这里插入图片描述][85f087837b014e71abadfd6e66db1829.png]  
输入：slices = \[1,2,3,4,5,6\]  
输出：10  
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

**示例 2：**  
![在这里插入图片描述][7b5709e8e76b434d8884a69635d8fa74.png]  
输入：slices = \[8,9,8,6,1,1\]  
输出：16  
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

**提示：**  
1 <= slices.length <= 500  
slices.length % 3 == 0  
1 <= slices\[i\] <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/pizza-with-3n-slices/

## 2.思路 ##

（1）动态规划

题可以转化成如下问题：**给一个长度为 3n 的环状序列，你可以在其中选择 n 个数，并且任意两个数不能相邻，求这 n 个数的最大和**。动态规划的解决方法和 [213.打家劫舍 II][213._ II] 这题较为相似。只不过求和的元素个数不同而已。

相关题目：  
[LeetCode\_动态规划\_中等\_213.打家劫舍 II][213._ II]

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public int maxSizeSlices(int[] slices) {
        
            int length = slices.length;
            int[] v1 = new int[length - 1];
            int[] v2 = new int[length - 1];
            System.arraycopy(slices, 1, v1, 0, length - 1);
            System.arraycopy(slices, 0, v2, 0, length - 1);
            return Math.max(calculate(v1), calculate(v2));
        }
    
        public int calculate(int[] slices) {
        
            int N = slices.length;
            int n = (N + 1) / 3;
            // dp[i][j] 表示在前 i 个数中选择了 j 个不相邻的数的最大和
            int[][] dp = new int[N][n + 1];
            for (int i = 0; i < N; i++) {
        
                Arrays.fill(dp[i], Integer.MIN_VALUE);
            }
            dp[0][0] = 0;
            dp[0][1] = slices[0];
            dp[1][0] = 0;
            dp[1][1] = Math.max(slices[0], slices[1]);
            for (int i = 2; i < N; i++) {
        
                dp[i][0] = 0;
                for (int j = 1; j <= n; j++) {
        
                	/*
                        不选择第 i 个数: dp[i][j] = dp[i - 1][j]
                        选择第 i 个数: dp[i][j] = dp[i - 2][j - 1] + slices[i]
                     */
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i]);
                }
            }
            return dp[N - 1][n];
        }
    }

[85f087837b014e71abadfd6e66db1829.png]: https://img-blog.csdnimg.cn/85f087837b014e71abadfd6e66db1829.png
[7b5709e8e76b434d8884a69635d8fa74.png]: https://img-blog.csdnimg.cn/7b5709e8e76b434d8884a69635d8fa74.png
[213._ II]: https://xgqngu.blog.csdn.net/article/details/123053121