0312.md

• 动态规划，dp[i][j] 表示 i 到 j 的区间（不戳破 i 和 j）能获得最大收益，k 为该区间内最后一个戳破的气球，状态转移方程为

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);

k 为最后戳破，所以最后 ijk 相邻
依次令 k = i + 1、i + 2、...、j - 1
其中得到的最大值即为 dp[i][j]

• 解法如下

class Solution {
 public:
  int maxCoins(vector<int>& nums) {
    nums.emplace(begin(nums), 1);
    nums.emplace_back(1);
    int sz = size(nums);
    vector<vector<int>> dp(sz, vector<int>(sz));
    for (int n = 2; n < sz; ++n) {
      for (int i = 0; i + n < sz; ++i) {
        for (int j = i + 1; j < i + n; ++j) {
          int t = dp[i][j] + dp[j][i + n] + nums[i] * nums[j] * nums[i + n];
          dp[i][i + n] = max(dp[i][i + n], t);
        }
      }
    }
    return dp[0][sz - 1];
  }
};