312 Burst Balloons

题目

312 Burst Balloons

题解

首先对问题进行下列分析

1. 问题可以被划分为子问题吗？

   打气球时，剩下的气球的maximum coins与已经被打掉的气球无关，因此本问题可以逐步转化为更小的子问题。

2. 较小规模的子问题可以用来辅助求解较大规模的子问题吗？

   假设我们已经知道规模在k以内的子问题的解，现在需要求解规模为k+1的问题的解。因为我们无法预先知道打气球的中间过程中各个气球的邻居，所以我们只有两种方法：①选出一个气球作为第一个打爆；②选出一个气球作为最后一个打爆。在气球\(x\)被打爆后，我们可以算出打爆它所得到的coins，然后加上\(x\)左边和\(x\)右边两部分的子问题之解。

   但是，第一种做法行不通，因为在第一个气球\(x\)被打爆后，\(x\)的左边部分会与右边部分相邻，从而产生出新的子问题，因此我们只能采用第二种方法，即把气球\(x\)放在最后打爆。

   记\(dp[left][right]\)为某一个问题的解，即打爆区间(left,right)内所有气球的maximum coins，\(nums[i]\)表示下标为\(i\)的气球上的数字，那么我们有 \(dp[left][right] = max(dp[left][right] , \\ dp[left][i] + nums[left] * nums[i] * nums[right] + dp[i][right]) \\ \text{for all i such that } left \lt i \lt right\)

因为气球\(i\)是最后才打爆的，所以打爆它得到的coins是\(nums[i]\)乘以两个边界上的值。因为气球\(i\)是在左右两边的气球都打爆后才被打爆的，所以可以直接利用左右两部分的解，即\(dp[left][i]\)和\(dp[i][right]\)进行计算。

本问题属于动态规划问题，求解这种问题的关键往往在于

1. 如何把问题划分成子问题
2. 如何利用较小规模的子问题求解较大规模的子问题

代码

class Solution
{
  public:
    int maxCoins(vector<int> &nums)
    {
        int numberSize = nums.size();
        int extendedSize = numberSize + 2;

        int extendedNums[extendedSize];
        extendedNums[0] = 1;
        for (int i = 0; i < numberSize; i++)
        {
            extendedNums[i + 1] = nums[i];
        }
        extendedNums[extendedSize - 1] = 1;

        int dynamicProgramming[extendedSize][extendedSize];
        for (int i = 0; i < extendedSize; i++)
        {
            for (int j = 0; j < extendedSize; j++)
            {
                dynamicProgramming[i][j] = 0;
            }
        }

        for (int k = 2; k < extendedSize; k++)
        {
            for (int left = 0; left < extendedSize - k; left++)
            {
                int right = left + k;
                for (int i = left + 1; i < right; i++)
                {
                    dynamicProgramming[left][right] = max(dynamicProgramming[left][right],
                                                          dynamicProgramming[left][i] +
                                                              extendedNums[left] * extendedNums[i] * extendedNums[right] +
                                                              dynamicProgramming[i][right]);
                }
            }
        }

        return dynamicProgramming[0][extendedSize - 1];
    }
};