Leetcode 312.Burst Balloons

发表于   |   分类于   |  

312.Burst Balloons的题目大意为：

有n个气球, 顺序编号为0~n-1. 如果戳破编号为i的气球, 你可以获得数量为 nums[left]*nums[i]*nums[right]的硬币. left和right代表气球i相邻的气球编号, 气球i戳破之后, left和right便是相邻的了. 找出你可以获得的最大硬币数量.

Naive的想法

首先我想, 如何保存状态?
假设4个气球数值为[3, 1, 5, 8]. 如果戳破3, 变为[1, 5, 8]. 如果戳破1, 变为[3, 5, 8]. 起初想用一位数(0或1)来表示气球是否被戳破. [3, 1, 5, 8]状态表示为(1, 1, 1, 1);[1, 5, 8]状态表示为(0, 1, 1, 1).[3, 5, 8]状态表示为(1, 0, 1, 1). 这样可以由状态(1, 1, 1, 1)转移到状态(0, 1, 1, 1)或(1, 0, 1, 1).
但是500个气球岂不是要大小为2^500的数来表示？遍历完每个状态的时间复杂度为O(2^n). 这样显然有问题.

联想到矩阵链乘法问题

以前见到过一道DP问题——矩阵链乘法和此题很像。
MatrixM

n个矩阵相乘, 因为不同的计算顺序会导致乘法计算次数不同。例如下图所示, 先计算A1*A2和先计算A2*A3的结果不同.
Mexample

那么如何选择计算顺序使得计算量最小?

用dp[i, j]表示Ai*A(i+1)* …*Aj的最优值, 有状态转移方程:

dp[i, j] = min{dp[i, k] + dp[k + 1, j] + p[i - 1] * p[k] * p[j]}

此题思路

如果用dp[i, j]表示戳破气球i~j可以获得的最大数目, 我们可以用最后戳破的气球k将[i, j]分成两部分:[i, k-1], [k+1, j]. 于是我们有了状态转移方程:

dp[i, j] = min{ dp[i, k - 1] + dp[k + 1, j] + nums[i - 1] * nums[k] * nums[j + 1]}
此外, 还需要注意k在i, j两个边界处的情况。

C++代码

github链接: 点这里

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
class Solution{
public:
    int maxCoins(vector<int>& nums){
        int n = nums.size();

        // n == 0
        if(n == 0)
            return 0;

        // 前后各插入一个1
        nums.insert(nums.begin(), 1);
        nums.push_back(1);

        // 二维数组
        int dp[n * n] = {};

        // assign dp[i, i]
        for(int i = 0;i < n;i++)
        {
            // dp[i, i] = nums[i-1 + 1] * nums[i + 1] * nums[i+1 + 1]
            dp[i * n + i] = nums[i] * nums[i + 1] * nums[i + 2];
        }

        // dp
        for(int j = 0;j < n;j++) // j: 0 -> n-1
        {
            for(int i = j - 1;i >= 0; i--)  // i: j-1 -> 0
            {
                for(int k = i;k <= j;k++)  //k: i -> j
                {
                    // nums[i-1 + 1] * nums[k + 1] * nums[j+1 + 1]
                    int sum = nums[i] * nums[k + 1] * nums[j + 2];;
                    // dp[i, j] = max(dp[i, k-1] + dp[k+1, j] + nums[i-1] * nums[j+1] + k)
                    if(k > i)
                        sum += dp[i * n + k - 1];
                    if(k < j)
                        sum += dp[(k + 1) * n + j];

                    dp[i * n + j] = max(dp[i * n + j], sum);
                }
            }
        }

        return dp[0 * n + n-1];
    }
};