LeetCode312. 戳气球

戳气球
区间DP，f[l][r],表示将区间【L，R】汇聚为两个数L，R所获得的金币
状态转移

f[l][r] = max(f[l][r], f[l][k] + f[k][r] + v[l] * v[r] * v[k]);
1

类似题目
能量项链

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        vector<int> v;
        v.push_back(1);
        for(auto c : nums)v.push_back(c);
        v.push_back(1);
        int n = v.size();
        vector<vector<int> > f(n, vector<int>(n));
        for(int len = 3; len <= n; len ++)
        {
            for(int l = 0; l + len - 1 < n;l ++)
            {
                int r = l + len - 1;
                for(int k = l + 1; k < r; k ++)
                {
                    f[l][r] = max(f[l][r], f[l][k] + f[k][r] + v[l] * v[r] * v[k]);
                }
            }
        }
        return f[0][n-1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

区间DP模板，

for (区间长度)
	for(固定区间)
		for(枚举分界点)
		
1
2
3
4