Hard

题目描述

有一个披萨，被切成了 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。

示例 2：

输入：slices = [8,9,8,6,1,1]
输出：16
解释：每一轮都选择大小为 8 的披萨。如果你选择大小为 9 的披萨，你的伙伴们就会选择大小为 8 的披萨。

提示：

  • 3 * n == slices.length
  • 1 <= slices.length <= 500
  • 1 <= slices[i] <= 1000

解题思路

这道题的关键是理解游戏规则的本质。通过分析可以发现，每当你选择一块披萨时，相邻的两块披萨都会被朋友拿走，这意味着你不能选择相邻的披萨块。

经过仔细分析，这个问题等价于：在一个环形数组中选择 n 个不相邻的元素，使得它们的和最大。

由于数组是环形的（第一个和最后一个元素相邻），我们需要分两种情况讨论：

  1. 不选择第一个元素：在 slices[1:] 中选择 n 个不相邻的元素
  2. 不选择最后一个元素：在 slices[:-1] 中选择 n 个不相邻的元素

对于每种情况，我们使用动态规划来解决。定义 dp[i][j] 表示从前 i 个元素中选择 j 个不相邻元素的最大和。状态转移方程为：

  • dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + slices[i-1])

第一项表示不选择当前元素，第二项表示选择当前元素（因此不能选择前一个元素）。

代码实现

class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size() / 3;
        
        // 情况1：不选择第一个元素
        vector<int> arr1(slices.begin() + 1, slices.end());
        
        // 情况2：不选择最后一个元素
        vector<int> arr2(slices.begin(), slices.end() - 1);
        
        return max(rob(arr1, n), rob(arr2, n));
    }
    
private:
    int rob(vector<int>& arr, int k) {
        int m = arr.size();
        if (k == 0) return 0;
        if (m == 0) return 0;
        
        vector<vector<int>> dp(m + 1, vector<int>(k + 1, 0));
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= min(i, k); j++) {
                dp[i][j] = dp[i-1][j];
                if (i >= 2) {
                    dp[i][j] = max(dp[i][j], dp[i-2][j-1] + arr[i-1]);
                } else if (j == 1) {
                    dp[i][j] = max(dp[i][j], arr[i-1]);
                }
            }
        }
        
        return dp[m][k];
    }
};

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices) // 3
        
        def rob(arr, k):
            m = len(arr)
            if k == 0 or m == 0:
                return 0
            
            dp = [[0] * (k + 1) for _ in range(m + 1)]
            
            for i in range(1, m + 1):
                for j in range(1, min(i, k) + 1):
                    dp[i][j] = dp[i-1][j]
                    if i >= 2:
                        dp[i][j] = max(dp[i][j], dp[i-2][j-1] + arr[i-1])
                    elif j == 1:
                        dp[i][j] = max(dp[i][j], arr[i-1])
            
            return dp[m][k]
        
        # 情况1：不选择第一个元素
        case1 = rob(slices[1:], n)
        # 情况2：不选择最后一个元素
        case2 = rob(slices[:-1], n)
        
        return max(case1, case2)

public class Solution {
    public int MaxSizeSlices(int[] slices) {
        int n = slices.Length / 3;
        
        // 情况1：不选择第一个元素
        int[] arr1 = new int[slices.Length - 1];
        Array.Copy(slices, 1, arr1, 0, slices.Length - 1);
        
        // 情况2：不选择最后一个元素
        int[] arr2 = new int[slices.Length - 1];
        Array.Copy(slices, 0, arr2, 0, slices.Length - 1);
        
        return Math.Max(Rob(arr1, n), Rob(arr2, n));
    }
    
    private int Rob(int[] arr, int k) {
        int m = arr.Length;
        if (k == 0 || m == 0) return 0;
        
        int[,] dp = new int[m + 1, k + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= Math.Min(i, k); j++) {
                dp[i, j] = dp[i - 1, j];
                if (i >= 2) {
                    dp[i, j] = Math.Max(dp[i, j], dp[i - 2, j - 1] + arr[i - 1]);
                } else if (j == 1) {
                    dp[i, j] = Math.Max(dp[i, j], arr[i - 1]);
                }
            }
        }
        
        return dp[m, k];
    }
}

var maxSizeSlices = function(slices) {
    const n = slices.length / 3;
    
    function rob(arr) {
        const m = arr.length;
        if (m === 0) return 0;
        if (n === 1) return Math.max(...arr);
        
        const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
        
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n && j <= i; j++) {
                dp[i][j] = dp[i-1][j];
                if (i >= 2) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-2][j-1] + arr[i-1]);
                } else if (j === 1) {
                    dp[i][j] = Math.max(dp[i][j], arr[i-1]);
                }
            }
        }
        
        return dp[m][n];
    }
    
    const case1 = rob(slices.slice(0, -1));
    const case2 = rob(slices.slice(1));
    
    return Math.max(case1, case2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n²)
空间复杂度O(n²)

其中 n 是披萨块数的三分之一。动态规划需要填充 O(n) × O(n) 的状态表，每个状态的计算时间为 O(1)。