分披萨问题概述

华为OD机试C卷中的分披萨问题是一个经典的动态规划与贪心算法结合的应用场景。题目描述通常为：给定一个圆形披萨，切成n块，每块有一个整数表示其大小。两个人轮流取披萨，每次只能取剩余的块中的连续1或2块。玩家希望自己取到的披萨总大小最大化，假设对手也采取最优策略。需要计算先手玩家能获得的最大总大小。

解题思路分析

该问题属于博弈论中的**“取石子游戏”变种，可通过贪心策略或DFS+记忆化搜索**解决。由于披萨是环形结构，需处理环形数组的展开问题（通常复制数组为两倍长度）。

核心思路是区间DP或DFS+记忆化：定义dp[l][r]表示在区间[l,r]内当前玩家能获得的最大值。状态转移方程为： [ dp[l][r] = \max \left( nums[l] - dp[l+1][r], nums[l] + nums[l+1] - dp[l+2][r] \right) ]

Java实现

public class Solution {
    public int maxPizza(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[][] dp = new int[2 * n][2 * n];
        
        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < 2 * n; l++) {
                int r = l + len - 1;
                if (len == 1) {
                    dp[l][r] = nums[l % n];
                } else {
                    dp[l][r] = Math.max(
                        nums[l % n] - dp[l + 1][r],
                        nums[l % n] + nums[(l + 1) % n] - dp[l + 2][r]
                    );
                }
            }
        }
        
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i][i + n - 1]);
        }
        return res;
    }
}

C++实现

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int maxPizza(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<vector<int>> dp(2 * n, vector<int>(2 * n, 0));
    
    for (int len = 1; len <= n; ++len) {
        for (int l = 0; l + len - 1 < 2 * n; ++l) {
            int r = l + len - 1;
            if (len == 1) {
                dp[l][r] = nums[l % n];
            } else {
                dp[l][r] = max(
                    nums[l % n] - dp[l + 1][r],
                    nums[l % n] + nums[(l + 1) % n] - dp[l + 2][r]
                );
            }
        }
    }
    
    int res = INT_MIN;
    for (int i = 0; i < n; ++i) {
        res = max(res, dp[i][i + n - 1]);
    }
    return res;
}

JavaScript实现

function maxPizza(nums) {
    const n = nums.length;
    if (n === 0) return 0;
    const dp = Array.from({ length: 2 * n }, () => new Array(2 * n).fill(0));
    
    for (let len = 1; len <= n; len++) {
        for (let l = 0; l + len - 1 < 2 * n; l++) {
            const r = l + len - 1;
            if (len === 1) {
                dp[l][r] = nums[l % n];
            } else {
                dp[l][r] = Math.max(
                    nums[l % n] - dp[l + 1][r],
                    nums[l % n] + nums[(l + 1) % n] - dp[l + 2][r]
                );
            }
        }
    }
    
    let res = -Infinity;
    for (let i = 0; i < n; i++) {
        res = Math.max(res, dp[i][i + n - 1]);
    }
    return res;
}

Python实现

def max_pizza(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [[0] * (2 * n) for _ in range(2 * n)]
    
    for length in range(1, n + 1):
        for l in range(2 * n):
            r = l + length - 1
            if r >= 2 * n:
                continue
            if length == 1:
                dp[l][r] = nums[l % n]
            else:
                dp[l][r] = max(
                    nums[l % n] - dp[l + 1][r],
                    nums[l % n] + nums[(l + 1) % n] - dp[l + 2][r]
                )
    
    res = -float('inf')
    for i in range(n):
        res = max(res, dp[i][i + n - 1])
    return res

算法复杂度分析

• 时间复杂度：O(n2)。双重循环遍历所有可能的区间。
• 空间复杂度：O(n2)。DP表格存储中间结果。

优化与变种

1. 环形展开：通过复制数组为2n长度，将环形问题转化为线性问题。
2. 记忆化DFS：可用递归实现，但需注意栈深度限制（Python默认递归深度约1000）。
3. 贪心尝试：若披萨块大小差异较大，可尝试贪心策略（如优先取较大块），但需验证正确性。