【深度优先搜索】312.戳气球

312. 戳气球（困难难度）

题目描述

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量。

输入：nums = [3,1,5,8]
输出：167
解释：
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

题目分析

戳破一个气球获得的金币数与相邻两个元素的值有关，被戳破的气球相当于不存在。

1、深度优先搜索

首先最简单的分析就是： 假设戳破第i个气球，将其标识为-1标识已经戳破，其获得的金币数可以由相邻的不为-1的数相乘获得，那么通过简单的深度优先搜索就可以写出代码。

// 方法一：回溯搜索，时间复杂度是O(n!)
    int maxCoins(vector<int>& nums) {
        int len=nums.size();
        int maxCoin=0;
        dfs(nums,0,len,0,maxCoin);
        return maxCoin;
    }
    void dfs(vector<int>& nums, int y, int length, int beforeCoins,int& maxCoin) {
        //回归条件
        if (y==length) {
            if (beforeCoins>maxCoin) maxCoin = beforeCoins;
            else return;
        }
        for (int i = 0; i < length; i++) {
            //略过已经戳破的气球
            if (nums[i] == -1) continue;
            //标记已经戳破的气球
            int temp = nums[i];
            nums[i] = -1;
            //获取上一个气球的数字
            int before = i - 1;
            int beforeNum = 0;
            while(before>-1&&nums[before]==-1)  before--;
            if (before < 0) beforeNum = 1;
            else beforeNum = nums[before];
            //获取下一个气球的数字
            int next = i + 1;
            int nextNum = 0;
            while(next<length&&nums[next]==-1) next++;
            if (next>length-1) nextNum = 1;
            else nextNum = nums[next];
            //计算戳破当前气球的coin
            int tempCoin = temp * nextNum * beforeNum;
            //递归进行下一戳
            dfs(nums, y+1, length,beforeCoins+tempCoin,maxCoin);
            //回溯尝试其它戳法
            nums[i] = temp;
        }
    }

第1层遍历了n个气球，第2层遍历了n-1个气球，第3层遍历了n-2个气球，总共要遍历n!，时间复杂度很高，在提交时会超时。

2、分治法+记忆化搜索

因为普通的深度优先搜索的时间复杂度是O(n!)，我们可以采用分治思想来缩小问题规模。

首先我们尝试每戳破一个气球i，以该气球为边界将气球数组[left,right]分为两部分[left,i-1]和[i+1,right]，使用这两个区间的解来求解原问题。假设戳破区间[left,right]的气球得到的最大金币数coin=dfs(left,right)，则当我们戳破气球i时，两边区间的最大值分别是 dfs(left, i-1 ) 与 dfs( i+1 , right)。

但是戳破气球 i时， 气球数组的相邻关系发生了改变，i-1 与 i+1 原本都与i相邻，而i 戳破后他们两个直接相邻了，而且先戳破 i+1 与先戳破 i-1 得到的结果将完全不同，也就是说两个子问题间发生了依赖。如果先戳破 i-1 ，则 i+1 左边的相邻气球变成了 i-2；反之 i-1 右边相邻的气球变成了 i+2 。两个子问题的处理顺序将影响到求解每个子问题的解。

既然两个子问题都依赖i和两个边界，那么我们可以重新定义我们的划分方式：

dfs(left,right)表示戳破区间（left,right）的气球得到的最大金币数（注意，left和right的气球都会保留）

这样当戳破气球i时，dfs(left,right)=dfs(left,i)+dfs(i,right)+x。此时left、i、right气球还没有戳破。

我们可以在原气球数组的开头和结尾分别添加一个值为1的元素，这样我们气球数组最初的0和len-1位置的气球是不用戳破的（因为是我们自己加入的，原题中没有），我们只需要戳破气球i即可，则x=nums[left]*nums[i]*[right]。

在上述状态转移方程中，我们需要搜索尝试戳破的气球i，i的取值显然是（left,right），而我们是要取最大金币，即在搜索时，只保存最大值即可。所以状态转移方程为：

dfs(left,right)=max(dfs(left,right),dfs(left,i)+dfs(i,right)+nums[left]*nums[i]*[right])

则实现代码如下：

// 方法二：记忆化搜索
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        int len=nums.size();
        vector<vector<int>> dp(len,vector<int>(len,-1));
        return dfs(nums,0,len-1,dp);
    }
    // 定义：在左开右开区间（left,right）戳破所有气球获得的最大金币数
    int dfs(vector<int>& nums,int left,int right,vector<vector<int>>&dp){
        if(left==right-1) return 0;// 如果区间为空，返回0
        if(dp[left][right]!=-1) return dp[left][right];// 如果区间已经搜索过，直接返回
        int max_v=0;// 
        // 尝试戳破（left,right）中的第i个气球
        for(int i=left+1;i<=right-1;++i){
            int temp=dfs(nums,left,i,dp)+dfs(nums,i,right,dp)+nums[i]*nums[left]*nums[right];
            dp[left][right]=max(max_v,temp);
        }
        dp[left][right]=max_v;
        return max_v;
    }

3、动态规划

记忆化搜索和动态规划基本就是同一种思路的两种不同版本：递归和迭代。

【状态定义】dp[left][right]表示戳破区间（left,right）的气球得到的最大金币数

【状态转换】dp[left][right]=max(dp[left][right],dp[left][i]+dp[i][right]+nums[left]*nums[i]*[right])，其中i的取值是（left,right）

【状态初始】根据定义right>=left+1,left的取值在[0,len-1]

int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        int len=nums.size();
        //dp[left][right] 定义：在左开右开区间（left,right）戳破所有气球获得的最大金币数
        vector<vector<int>> dp(len,vector<int>(len,0));
        for(int l=2;l<=len;l++){
            for(int left=0;left<=len-l;left++){
                int right=left+l-1;
                // 尝试戳破（left,right）中的第i个气球
                for(int k=left+1;k<=right-1;k++){
                    int temp=dp[left][k]+dp[k][right]+nums[left]*nums[k]*nums[right];
                    dp[left][right] = max(dp[left][right],temp);
                }
            }
        }
        return dp[0][len-1];
    }