本页目录

LeetCode 312.戳气球

原题链接：戳气球

区间DP，假设dp[l][r]表示戳破开区间 $(l, r)$ 内的气球获得的最大硬币数。由于边界视作数值为1的气球，给数组nums的首尾都插入1，最后的答案也恰好是dp[0][n+1]（根据定义，不包含插入的两个端点）。

转移方程为：

d p (l, r) = max_{l < m < r} d p (l, m) + d p (m, r) + n u m s (l) \times n u m s (m) \times n u m s (r)

#define N 305
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n=nums.size();//在首尾插入1之前，数组的原始长度
        int dp[N][N]={};//dp[l][r]表示戳破(l,r)开区间所有气球获得的最大硬币数
        nums.emplace_back(1);
        nums.emplace(nums.begin(),1);
        for(int d=2;d<=n+1;d++)//枚举区间长度
        {
            for(int l=0;l+d<=n+1;l++)//左端点
            {
                int r=l+d;
                for(int m=l+1;m<=r-1;m++)//分割点
                {
                    dp[l][r]=max(
                        dp[l][r],
                        dp[l][m]+dp[m][r]+nums[l]*nums[m]*nums[r]
                    );
                }
            }
        }
        return dp[0][n+1];
    }
};