Leetcode|312. 戳气球（反向思维+区间动态规划）

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        vector<int> scores(nums.size() + 2, 0);
        // 收尾补充1
        scores.front() = 1; scores.back() = 1; 
        int size = scores.size();
        for (int i = 1; i < size - 1; i++) scores[i] = nums[i - 1]; 
        // dp数组含义：开区间(i, j)内戳破气球获得的最大硬币数量
        vector<vector<int>> dp(size, vector<int>(size, 0));

        for (int i = size - 1; i >= 0; i--)
            for (int j = i + 1; j < size; j++) {
                // [关键]：k表最后1个戳破的气球索引
                // 若k表第1个戳破的气球，则尾部为scores[k-1]*scores[k]*scores[k+1]导致子问题相互依赖）
                for (int k = i + 1; k < j; k++)
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + scores[i]*scores[k]*scores[j]);
            }
        return dp[0][size - 1];
    }
};