戳气球

01 Sep 2024 in Algorithm Pageviews

leetcode dp!

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。当戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或者 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量。

示例1：

输入：nums = [3, 1, 5, 8]

输出：167

解释：

nums = [3, 1, 5, 8] - - -> [3, 5, 8] - - -> [3, 8] - - -> [8] - - -> []

coins = 3 * 1 * 5 + 3 * 5 * 8 + 1 * 3 * 8 + 1 * 8 * 1 = 167

示例2：

输入：nums = [1, 5]

输出：10

代码实现如下:

Solution {
public:
    int Solve(int l, int r)
    {
        if (r - l < 2) {
            return 0;
        }
        
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        
        for (int m = l + 1; m < r; m++) {
            int sum = num_[l] * num_[m] * num_[r];
            sum += Solve(l, m) + Solve(m, r);
            dp[l][r] = max(sum, dp[l][r]);
        }
        return dp[l][r];
    }

    int MaxCoins(const vector<int> &nums)
    {
        int n = nums.size();
        num_.resize(n + 2, 1);
        for (int i = 1; i <= n; i++) {
            num_[i] = nums[i - 1];
        }

        dp.resize(n + 2, vector<int>(n + 2, -1));
        return Solve(0, n + 1);
    }

private:
    vector<vector<int>> dp;
    vector<int> num_;
};