Description

给定\(n\)个元素,值为\(a_i\)。每取出一个元素\(i\)可以得到贡献\(a_{i-1} * a_i * a_{i+1}\),注意这里\(i-1\)和\(i+1\)指的是当前相邻的元素,如果没有相邻元素则当作1。求取出所有元素的最大贡献。

Constraints

  • \(1 \le n \le 300\)
  • \(0 \le a_i \le 100\)

Solution

一眼区间DP。

设\(dp[l][r]\)为区间\((l, r)\)的最大贡献,枚举区间中最后一个取出的元素\(i\),那么递推公式为\(dp[l][r] = max_{i=l+1}^{r-1}\{dp[l][i] + a[i-1]*a[i]*a[i+1] + dp[i][r]\}\)。

这里有点诀窍:

  • \(a\)两端加入元素\(1\),避免边界处理;
  • \(dp[l][r]\)不统计两端取出(使用开区间),因此枚举\(i\)时\(l\)和\(r\)必然存在。

Code

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int dp[305][305];
        memset(dp, -1, sizeof dp);
        nums.emplace(nums.begin(), 1);
        nums.emplace(nums.end(), 1);
        auto DP = [&](auto &&self, int l, int r) -> int {
            // dp[l][r] does NOT include l and r
            if(r-l+1 <= 2) return 0;
            if(~dp[l][r]) return dp[l][r];
            int val = 0;
            for(int x = l+1; x <= r-1; x++) {
                int tmp = self(self, l, x)
                        // x: last one to be killed
                        + nums[x]*nums[l]*nums[r]
                        + self(self, x, r);
                val = max(val, tmp);
            }
            return dp[l][r] = val;
        };
        return DP(DP, 0, nums.size()-1);
    }
};

LeetCode-312 Burst Balloons