LC312: Burst Balloons

작성일

https://leetcode.com/problems/burst-balloons/

  • 역발상이 중요한 DP 문제, 사건을 역순으로 진행해야만 DP가 손쉽게 적용된다. 역순으로 진행할 경우 좌우에 있는 풍선의 가치를 고정할 수 있기 때문이다.
  • 점화식은 역시나 조건을 먼저 체크해줘야 간단해진다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> data;
    vector<vector<int>> dp;
    int go(int s, int e) {
        if(s > e) return 0;
        if(dp[s][e] != -1) return dp[s][e];
        for(int i = s; i <= e; i++)
            dp[s][e] = max(dp[s][e], go(s,i-1) + data[s-1] * data[i] * data[e+1] + go(i+1, e));
        return dp[s][e];
    }
    
    int maxCoins(vector<int>& nums) {
        data.push_back(1);
        data.insert(data.end(), nums.begin(), nums.end());
        data.push_back(1);
        int N = nums.size();
        dp.resize(N+1, vector<int>(N+1,-1));
        return go(1, N);
    }
};