312. Burst Balloons

week12

难度：Hard

题目链接

题目描述

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

  • You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
            coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

题目分析

  题意就是给予一连串的气球，每个气球上都有分数，当点击气球后，气球消失，获得的分数即是被点击的气球*两边的气球。找出可获得的最大分数。

解题思路

  这道题明示使用动态规划，考虑将问题分为多个子问题解决，假设按点击的顺序计算，每次点击都会使被点击的气球消失，再根据剩下的元素来构造新的数组，那么这个问题又变成了新的环境，难以简单地复用解决。假设按倒推的方式思考，假设最后一个气球被戳破，那么它左边或者右边的气球不会受到对方的影响，因为隔着一个气球始终在它们的中间，所以左边和右边的气球戳破顺序就可以分开计算，化简成多个小问题。

  假设第i个气球为最后戳破的气球，max[a][b]为第a到第b个气球获得的最大分数，那么问题的解就变为：$$maxCoins[0][n - 1] = maxCoins[0][i - 1] + maxCoins[i + 1][n - 1] + nums[left] * nums[i] * nums[right]$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
public:
  int maxCoins(vector<int> &nums)
  {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 2; i < n; i++)
    {
      for (int l = 0; l < n - i; l++)
      {
        int r = l + i;
        for (int j = l + 1; j < r; j++)
        {
          dp[l][r] = max(dp[l][r], dp[l][j] + dp[j][r] + nums[l] * nums[r] * nums[j]);
        }
      }
    }
    return dp[0][n - 1];
  }
};

结果反思

测试
测试

  这个算法还是比较简洁的，没有什么多余的东西，就是纯dp。

代码分析

  因为要考虑到戳破气球时，有边界的问题，所以在两边加上两个无法被戳破的分数为1的气球，构成n+2的新数组，最后的状态转移为：$$Coins[left][right] = max(Coins[left][right], Coins[left][i] + Coins[i][right] + nums[left] * nums[right] * nums[i]);$$

总结

  这个题目说明了动态规划有时候按正向推导分解问题可能会分解不了多个较小的子问题，在这种时候要尝试逆向思维，反过来思考到达最后的状态时，要经过哪些状态。这道题有点和上两周那道Freedom Trail即辐射4旋转字符串一样，都是从最后的状态开始，从而分解成多个子问题。