华为OD机试C卷 - 分披萨 - 贪心与DFS算法解析

问题描述

题目要求将一块圆形披萨分成若干块，每块披萨的大小可能不同。给定一个整数数组表示每块披萨的大小，两个人轮流选取披萨块。每次只能从剩余的披萨块中选择当前最左边或最右边的块。假设两人都采取最优策略，求先手能获得的最大披萨总大小。

贪心算法分析

贪心算法通常用于每一步选择当前最优解，但在此问题中，单纯的贪心策略可能无法得到全局最优解。例如，如果当前玩家选择当前较大的块，可能让对手在后续步骤中获得更大的优势。因此，贪心算法在此问题中并不适用。

DFS与动态规划

深度优先搜索（DFS）结合记忆化技术可以高效解决此问题。通过递归模拟每一步的选择，并缓存中间结果以避免重复计算。

定义状态为dp[l][r]，表示在区间[l, r]内当前玩家能获得的最大分数。状态转移方程为： [ dp[l][r] = \max(pizza[l] - dp[l+1][r], pizza[r] - dp[l][r-1]) ] 其中pizza[l] - dp[l+1][r]表示选择左边块后的净收益，pizza[r] - dp[l][r-1]表示选择右边块后的净收益。

代码实现

Java

public class Solution {
    public int maxPizza(int[] pizza) {
        int n = pizza.length;
        int[][] dp = new int[n][n];
        for (int l = n - 1; l >= 0; l--) {
            for (int r = l; r < n; r++) {
                if (l == r) {
                    dp[l][r] = pizza[l];
                } else {
                    dp[l][r] = Math.max(pizza[l] - dp[l + 1][r], pizza[r] - dp[l][r - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

C++

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

int maxPizza(vector<int>& pizza) {
    int n = pizza.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int l = n - 1; l >= 0; l--) {
        for (int r = l; r < n; r++) {
            if (l == r) {
                dp[l][r] = pizza[l];
            } else {
                dp[l][r] = max(pizza[l] - dp[l + 1][r], pizza[r] - dp[l][r - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

JavaScript

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

Python

def max_pizza(pizza):
    n = len(pizza)
    dp = [[0] * n for _ in range(n)]
    for l in range(n - 1, -1, -1):
        for r in range(l, n):
            if l == r:
                dp[l][r] = pizza[l]
            else:
                dp[l][r] = max(pizza[l] - dp[l + 1][r], pizza[r] - dp[l][r - 1])
    return dp[0][n - 1]

复杂度分析

• 时间复杂度：O(n2)，其中n为披萨块的数量。动态规划表需要填充n2个状态。
• 空间复杂度：O(n2)，用于存储动态规划表。可以通过滚动数组优化到O(n)。

实际应用

该问题可以扩展到其他类似的博弈场景，如石子游戏或卡片分配问题。掌握动态规划与DFS的结合使用，对解决类似的优化问题非常有帮助。