LeetCode 1388：环形数组动态规划解3n披萨问题-育师

1. 问题背景与题目解析

LeetCode 1388题"3n块披萨"是一个经典的动态规划问题，题目描述如下：你有一块披萨，上面有3n块切片，每块切片的大小不同。你需要选择n块切片，但选择的规则是：不能选择相邻的两块切片（即如果你选择了第i块切片，就不能选择第i-1和i+1块切片）。目标是最大化所选n块切片的大小总和。

这道题看似简单，但实际上考察了对环形数组和动态规划的综合应用能力。题目给出的函数签名是：

public int maxSizeSlices(int[] slices)

其中slices数组表示披萨上各切片的大小，我们需要返回能选择的最大总和。这个问题可以转化为：在一个环形数组中，选择不相邻的n个元素，使它们的和最大。

2. 解题思路分析

2.1 问题转化

首先，我们需要认识到这个问题与经典的"打家劫舍"问题类似，但有两个关键区别：

数组是环形的（首尾相连）
需要选择恰好n个元素，而不是尽可能多的元素

对于环形数组问题，常见的处理方法是将其转化为两个线性问题：

不考虑第一个元素（即只能在第二个到最后一个元素中选择）
不考虑最后一个元素（即只能在第一个到倒数第二个元素中选择）

然后分别求解这两个线性问题，取较大的结果作为最终答案。

2.2 动态规划状态定义

对于线性数组的情况，我们可以定义dp[i][j]表示在前i个元素中选择了j个元素的最大和。状态转移方程为：

dp[i][j] = max( dp[i-1][j], // 不选第i个元素 dp[i-2][j-1] + slices[i] // 选第i个元素 )

其中边界条件是：

dp[0][j] = -∞ (j > 0)，因为无法从0个元素中选择j>0个元素
dp[i][0] = 0，因为选择0个元素的和为0

2.3 环形数组处理

对于环形数组，我们需要分别计算两种情况：

不选第一个元素，在slices[1...n-1]中选择n个元素
不选最后一个元素，在slices[0...n-2]中选择n个元素

最终结果是这两种情况的最大值。

3. 代码实现与优化

3.1 基础实现

基于上述思路，我们可以实现如下Java代码：

public int maxSizeSlices(int[] slices) { int n = slices.length; int k = n / 3; // 需要选择k=n/3个元素 // 情况1：不选第一个元素 int[][] dp1 = new int[n][k+1]; for (int i = 1; i < n; i++) { for (int j = 1; j <= k; j++) { if (i == 1) { dp1[i][j] = Math.max(slices[i], dp1[i-1][j]); } else { dp1[i][j] = Math.max(dp1[i-1][j], dp1[i-2][j-1] + slices[i]); } } } // 情况2：不选最后一个元素 int[][] dp2 = new int[n][k+1]; for (int i = 0; i < n-1; i++) { for (int j = 1; j <= k; j++) { if (i == 0) { dp2[i][j] = slices[i]; } else if (i == 1) { dp2[i][j] = Math.max(slices[i], dp2[i-1][j]); } else { dp2[i][j] = Math.max(dp2[i-1][j], dp2[i-2][j-1] + slices[i]); } } } return Math.max(dp1[n-1][k], dp2[n-2][k]); }

3.2 空间优化

注意到dp[i][j]只依赖于dp[i-1][j]和dp[i-2][j-1]，我们可以将空间复杂度从O(nk)优化到O(k)：

public int maxSizeSlices(int[] slices) { int n = slices.length; int k = n / 3; // 情况1：不选第一个元素 int[] dp1_prev = new int[k+1]; int[] dp1_curr = new int[k+1]; int[] dp1_next = new int[k+1]; for (int i = 1; i < n; i++) { for (int j = 1; j <= k; j++) { dp1_next[j] = Math.max(dp1_curr[j], dp1_prev[j-1] + slices[i]); } dp1_prev = dp1_curr; dp1_curr = dp1_next; dp1_next = new int[k+1]; } // 情况2：不选最后一个元素 int[] dp2_prev = new int[k+1]; int[] dp2_curr = new int[k+1]; int[] dp2_next = new int[k+1]; for (int i = 0; i < n-1; i++) { for (int j = 1; j <= k; j++) { if (i == 0) { dp2_next[j] = slices[i]; } else { dp2_next[j] = Math.max(dp2_curr[j], dp2_prev[j-1] + slices[i]); } } dp2_prev = dp2_curr; dp2_curr = dp2_next; dp2_next = new int[k+1]; } return Math.max(dp1_curr[k], dp2_curr[k]); }

4. 复杂度分析与边界条件

4.1 时间复杂度

算法的时间复杂度主要取决于两层循环：

外层循环遍历数组，O(n)
内层循环遍历选择的元素数量，O(k)
总时间复杂度为O(nk) = O(n^2)，因为k = n/3

4.2 空间复杂度

经过空间优化后，我们只需要维护三个长度为k+1的数组，因此空间复杂度为O(k) = O(n)

4.3 边界条件处理

需要特别注意以下边界条件：

当n=1时，只能选择这唯一的一块切片
当n=3时，必须选择其中一块切片（因为不能选相邻的两块）
当所有切片大小相同时，任意选择n个不相邻的切片即可

5. 测试用例与验证

为了验证代码的正确性，我们可以设计以下几组测试用例：

// 测试用例1：简单情况 int[] slices1 = {1,2,3,4,5,6}; assert maxSizeSlices(slices1) == 10; // 选择2,4,6 // 测试用例2：环形情况 int[] slices2 = {8,9,8,6,1,1}; assert maxSizeSlices(slices2) == 16; // 选择第一个和第三个8 // 测试用例3：所有元素相同 int[] slices3 = {3,3,3,3,3,3}; assert maxSizeSlices(slices3) == 9; // 选择任意三个不相邻的3 // 测试用例4：边界情况n=1 int[] slices4 = {5}; assert maxSizeSlices(slices4) == 5; // 测试用例5：边界情况n=3 int[] slices5 = {1,2,3}; assert maxSizeSlices(slices5) == 3; // 只能选择中间那个

6. 实际应用与扩展

6.1 实际问题中的应用

这类问题在实际中有很多应用场景，例如：

资源分配问题：在有限的资源中选择最优组合，且某些资源不能同时选择
任务调度：选择不相邻的时间段执行任务以获得最大收益
网络路由：选择不相邻的节点进行数据传输

6.2 算法扩展

基于这个问题的解法，我们可以进一步思考：

如果披萨不是环形的，而是线性的，如何简化解法？
如果可以选择任意数量的切片（不一定是n块），但总和最大且不相邻，如何解决？
如果切片的选择限制更复杂（比如不能选择相邻的三个切片），如何修改算法？

6.3 性能优化

对于大规模数据，可以考虑以下优化：

使用记忆化搜索替代动态规划，减少不必要的计算
并行计算两种情况的动态规划
使用更高效的数据结构存储中间结果

7. 常见错误与调试技巧

在解决这个问题时，容易犯以下错误：

忘记处理环形数组的情况，直接当作线性数组处理
动态规划状态转移方程写错，特别是边界条件处理不当
空间优化时混淆了数组的更新顺序

调试技巧：

打印中间dp表的值，验证是否符合预期
从小规模测试用例开始，逐步增加复杂度
对比线性情况和环形情况的结果，检查差异是否合理

8. 与其他LeetCode题目的联系

这个问题与以下几个LeetCode题目有相似之处：

1. 打家劫舍：线性数组中选择不相邻元素的最大和
1. 打家劫舍II：环形数组中选择不相邻元素的最大和
1. 打家劫舍III：树形结构中选择不相邻节点的最大和

理解这些题目的共性和差异，有助于形成系统的动态规划解题思路。

LeetCode 1388：环形数组动态规划解3n披萨问题