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);
}
};