LeetCode 312.戳气球

#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];
    }
};