関小君刷题记

题目大意：

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 的披萨，这种情况下你的总和不是最大的。

示例 3：

输入：slices = [4,1,2,5,8,3,1,9,7]
输出：21

示例 4：

输入：slices = [3,1,2]
输出：3

提示：

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1388

解题思路分析：

本题的题意很明确，当自己选完一块披萨之后，另外两个人会拿走与之相邻的两片，因此我们可以得到一个很重要的结论，即无论如何，你也不可能拿到相邻的两片披萨。换句话说，如果我们拿到的所有披萨都不相邻，则一定是一个合理的情况。因此本题目就转化为，在一个长度为3n的数组中找到n个不相邻并且和最大数字。另外注意一点，由于披萨是圆形，因此，数组中首元素与尾元素同样属于相邻元素。

由于要保证首尾两个数字不能同时选择，因此我们可以从数组的第1到3n-1位范围内选取不相邻并且和最大的n个数，再从第2位到第3n位选取，两者最大值即是返回结果。

解题时，我们可以考虑使用递归加记忆数组的思路。递归函数需要三个重要参数，数组起始下标，数组结束下标，以及当前已选择的个数。当已选择个数等于n时结束递归。递归函数中，我们从起始下标循环至结束下标，循环中任意当前数字都是可选择的对象，选择一个数字后，我们递归到子问题继续求解，递归时，由于不能选择与当前相邻的元素，因此起始下标变为当前下标加2，结束下标不变，已选择个数加一。当前数值加上子问题递归结果为当前结果，循环后取得最大结果作为本层递归的返回值。

实现代码：

public int maxSizeSlices(int[] slices) {
    // 记忆数组
    int[][] memo=new int[slices.length][slices.length/3+1];
    // 从第1位到倒数第2位范围内选择的最大的结果
    int res1= help(slices,0,slices.length-2,0,memo);
    memo=new int[slices.length][slices.length/3+1];
    // 从第2位到倒数第1位范围内选择的最大的结果
    int res2= help(slices,1,slices.length-1,0,memo);
    // 两者最大值为返回结果
    return Math.max(res1, res2);
}
int help(int[] slices,int start,int end,int count, int[][] memo){
    // 如果已经选择完所有披萨，返回0
    if(count==slices.length/3) return 0;
    // 如果剩余披萨中不够选择，返回-1
    if(slices.length/3-count>(end-start+2)/2) return -1;
    if(memo[start][count]>0)return memo[start][count];
    int max=0;
    for(int i=start;i<=end;i++){
        int sum=help(slices,i+2,end,count+1,memo);
        if(sum==-1) break;
        max=Math.max(max,slices[i]+sum);
    }
    memo[start][count]=max;
    return max;
}

本题解法执行时间为108ms。

Runtime: 108 ms, faster than 20.00% of Java online submissions for Pizza With 3n Slices.

Memory Usage: 40.9 MB, less than 100.00% of Java online submissions for Pizza With 3n Slices.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1388-pizza-with-3n-slices-解题思路分析/