LeetCode 1388：环形数组动态规划解3n披萨问题-北京尧图网络

1. 问题背景与题目解析LeetCode 1388题3n块披萨是一个经典的动态规划问题题目描述如下你有一块披萨上面有3n块切片每块切片的大小不同。你需要选择n块切片但选择的规则是不能选择相邻的两块切片即如果你选择了第i块切片就不能选择第i-1和i1块切片。目标是最大化所选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个元素中选择j0个元素dp[i][0] 0因为选择0个元素的和为02.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; // 需要选择kn/3个元素 // 情况1不选第一个元素 int[][] dp1 new int[n][k1]; 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][k1]; 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[k1]; int[] dp1_curr new int[k1]; int[] dp1_next new int[k1]; 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[k1]; } // 情况2不选最后一个元素 int[] dp2_prev new int[k1]; int[] dp2_curr new int[k1]; int[] dp2_next new int[k1]; 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[k1]; } return Math.max(dp1_curr[k], dp2_curr[k]); }4. 复杂度分析与边界条件4.1 时间复杂度算法的时间复杂度主要取决于两层循环外层循环遍历数组O(n)内层循环遍历选择的元素数量O(k)总时间复杂度为O(nk) O(n^2)因为k n/34.2 空间复杂度经过空间优化后我们只需要维护三个长度为k1的数组因此空间复杂度为O(k) O(n)4.3 边界条件处理需要特别注意以下边界条件当n1时只能选择这唯一的一块切片当n3时必须选择其中一块切片因为不能选相邻的两块当所有切片大小相同时任意选择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边界情况n1 int[] slices4 {5}; assert maxSizeSlices(slices4) 5; // 测试用例5边界情况n3 int[] slices5 {1,2,3}; assert maxSizeSlices(slices5) 3; // 只能选择中间那个6. 实际应用与扩展6.1 实际问题中的应用这类问题在实际中有很多应用场景例如资源分配问题在有限的资源中选择最优组合且某些资源不能同时选择任务调度选择不相邻的时间段执行任务以获得最大收益网络路由选择不相邻的节点进行数据传输6.2 算法扩展基于这个问题的解法我们可以进一步思考如果披萨不是环形的而是线性的如何简化解法如果可以选择任意数量的切片不一定是n块但总和最大且不相邻如何解决如果切片的选择限制更复杂比如不能选择相邻的三个切片如何修改算法6.3 性能优化对于大规模数据可以考虑以下优化使用记忆化搜索替代动态规划减少不必要的计算并行计算两种情况的动态规划使用更高效的数据结构存储中间结果7. 常见错误与调试技巧在解决这个问题时容易犯以下错误忘记处理环形数组的情况直接当作线性数组处理动态规划状态转移方程写错特别是边界条件处理不当空间优化时混淆了数组的更新顺序调试技巧打印中间dp表的值验证是否符合预期从小规模测试用例开始逐步增加复杂度对比线性情况和环形情况的结果检查差异是否合理8. 与其他LeetCode题目的联系这个问题与以下几个LeetCode题目有相似之处打家劫舍线性数组中选择不相邻元素的最大和打家劫舍II环形数组中选择不相邻元素的最大和打家劫舍III树形结构中选择不相邻节点的最大和理解这些题目的共性和差异有助于形成系统的动态规划解题思路。

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

相关推荐

Python动漫数据分析实战：从TB级处理到可视化看板

SQLite FTS5+BM25构建轻量级context-mode上下文检索系统

NE5532高中低音调音电路设计：电源、前级与负反馈网络三段式拆解

更多资讯

MVDR与常规波束形成对比：原理、Python实现与工程避坑指南

风电负荷聚类与出力预测：从物理特征提取到调度可用预测

【免费开源】ROSTCM6词频统计软件：面向人文社科研究的免费文本分析工具

压缩感知实战：从CScode.zip到OMP重构与参数调优

自研Blender绑定工具OpenRig：从骨骼到控制器的完整方案

教育论文数据分析的AI解决方案与效率提升

今日更新

AI智能体开发实战：从技术原理到商业落地

OpenShell 完全定制指南：从安装到深度配置，打造高效 Windows 开始菜单

Superpowers技能体系全解析：从Skills引入到安装的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？