披萨题库
3n 块披萨
给你一个披萨，它由 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 的披萨，这种情况下你的总和不是最大的。
整体思路: 将问题转化为 给一个长度为 3n 的环状序列，你可以在其中选择 n 个数，并且任意两个数不能相邻，求这 n 个数的最大值。
方案 动态规划
思路:
- 状态定义: dp[i][j] 表示在前 i 个数中选择了 j 个不相邻的数的最大和
- 状态转移方程: dp[i][j] 可以从两个位置转移而来
- 如果我们选择了第 i 个数，那么第 i - 1 个数不能被选择，相当于需要在前 i - 2 个数中选择 j - 1 个，即：dp[i][j]=dp[i−2][j−1]+slices[i]
- 如果我们没有选择第 i 个数，那么需要在前 i - 1 个数中选择 j 个，即：dp[i][j]=dp[i−1][j]
- 取两者的最大值即为状态转移方程：dp[i][j]=max(dp[i−2][j−1]+slices[i],dp[i−1][j])
- 初始化状态:
- 问题答案: 环状序列相较于普通序列，相当于添加了一个限制：普通序列中的第一个和最后一个数不能同时选。这样以来，我们只需要对普通序列进行两遍动态即可得到答案，第一遍动态规划中我们删去普通序列中的第一个数，表示我们不会选第一个数；第二遍动态规划中我们删去普通序列中的最后一个数，表示我们不会选最后一个数。将这两遍动态规划得到的结果去较大值，即为在环状序列上的答案。
:::details 点击查看代码
function calculate(nums){
let len=nums.length;
let choose=Math.floor((len+1)/3);
let dp=new Array(len+1).fill(0).map(value=>new Array(choose+1).fill(0));
for(let i=1;i<=len;i++){
for(let j=1;j<=choose;j++){
dp[i][j]=Math.max(dp[i-1][j],(i-2>=0?dp[i-2][j-1]:0)+nums[i-1]);
}
}
return dp[len][choose];
}
function maxSizeSlices(nums) {
let nums1=nums.slice(1);
let nums2=nums.slice(0,-1);
return Math.max(calculate(nums1),calculate(nums2));
};
:::
性能分析:
- 时间复杂度：O(N^2)，其中 N 是数组 slices 的长度。
- 空间复杂度：O(N^2)，即存储动态规划计算的状态需要使用的空间。