Leetcode:312. Burst Balloons

Posted on | Comments: | Views:
DP

312. Burst Balloons

题目理解:

给出一串气球, 每炸裂一个气球会有 left*right*itself 的得分, 同时气球消失, 找出炸裂这一串气球能获得的最大分数

思路:

用 f[i][j] 记录状态, 表示在其他气球完好的情况下, 炸裂[i, j]气球的最大得分;
所以问题的答案就是 f[sqrt(n)][n]


要写出状态转移方程要考虑的问题: 假设[i,j]中除了 f[i][j], 其他例如 f[i+1][j], f[i][j-1]之类的子问题都求出来了, 如何求 f[i][j] 呢
可以将[i,j]分为三部分: [i,k-1], [k,k], [k+1, j], 前后两部分的得分由 f[i][k-1] 和 f[k+1][j] 算出, 根据 f[i][j] 的定义, 剩下的[k,k], 前后的气球都炸裂了, 所以 f[k,k] 为 point(i-1)*point(k)*point(j+1)
这样就能够写出状态转移方程 f[i][j] = max(i<=k<=j){ f[i][k-1] + f[k+1][j] + p(i-1)*p(k)*p(j+1) }


我最终实现的时候使用了递归, 当然是记忆化的递归, 不过看起来效率还是挺低的, 好处就是编程难度较低; 初始状态需要算每个 f[i][i];

小结:

这道题明显是矩阵乘法的变种, 最初在想状态转移方程的时候想了挺多, 这个过程蛮艰难的

Submission Detail:

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>

using namespace std;


class Solution {
public:
    int f[501][501];
    int n;
    vector<int> num;
    int maxCoins(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        if (nums.size() == 1) {
            return nums[0];
        }
        num = nums;
        n = nums.size()-1;
        for (int i = 0; i < n+1; ++i) {
            for (int j = 0; j < n+1; ++j) {
                f[i][j] = -1;
            }
        }
        f[0][0] = nums[0]*nums[1];
        f[n][n] = nums[n-1]*nums[n];
        for (int i = 1; i < n; ++i) {
            f[i][i] = nums[i-1]*nums[i]*nums[i+1];
        }
        find(0, n);
        for (int i = 0; i < n+1; ++i) {
            for (int j = 0; j < n+1; ++j) {
                cout << f[i][j] << ' ';
            }
            cout << endl;
        }
        return f[0][n];
    }
    void find(int x, int y) {
        //cout << x << ' ' << y << endl;
        if (f[x][y] != -1) {
            return;
        }
        
        int max = 0;
        int l, r, ll, rr, ch;
        for (int k = x; k <= y; ++k) {
            if (k!=x && f[x][k-1] == -1) {
                find(x, k-1);
            }
            l = k!=x?f[x][k-1]:0;
            ll = x==0?1:num[x-1];
            if (k!=y && f[k+1][y] == -1) {
                find(k+1, y);
            }
            r = k!=y?f[k+1][y]:0;
            rr = y==n?1:num[y+1];
            if (max < l + r + ll * num[k] * rr) {
                max = l + r + ll * num[k] * rr;
                ch = k;
            }
        }
        //cout << ch << ' ';
        f[x][y] = max;
    
    }
};