[depth first search] 312 Poke balloon

312. Poke a balloon （ It's difficult ）

Title Description

Yes n A balloon , The number is 0 To n - 1, Each balloon is marked with a number , There are arrays of these numbers nums in . Now I ask you to prick all the balloons . Pierce the second i A balloon , You can get nums[i - 1] * nums[i] * nums[i + 1] Coin . there i - 1 and i + 1 For and on behalf of i The serial number of the two adjacent balloons . If i - 1 or i + 1 Beyond the bounds of the array , Then think of it as a number for 1 The balloon . Find the maximum number of coins you can get .

Input ：nums = [3,1,5,8]
Output ：167
explain ：
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

Topic analysis

The number of gold coins obtained by puncturing a balloon is the same as Two adjacent elements The value of , A punctured balloon is equivalent to nonexistence .

1、 Depth-first search

The first and simplest analysis is ： Suppose you break the i A balloon , Identify it as -1 The logo has been punctured , The number of gold coins obtained can be determined by Adjacent is not -1 Number of numbers Multiply to get , So by simply Depth-first search You can write code .

//  Method 1 ： Backtracking search , The time complexity is 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) {
        // Regression conditions 
        if (y==length) {
            if (beforeCoins>maxCoin) maxCoin = beforeCoins;
            else return;
        }
        for (int i = 0; i < length; i++) {
            // Skip the punctured balloon 
            if (nums[i] == -1) continue;
            // Mark a balloon that has been punctured 
            int temp = nums[i];
            nums[i] = -1;
            // Get the number of the previous balloon 
            int before = i - 1;
            int beforeNum = 0;
            while(before>-1&&nums[before]==-1)  before--;
            if (before < 0) beforeNum = 1;
            else beforeNum = nums[before];
            // Get the number of the next balloon 
            int next = i + 1;
            int nextNum = 0;
            while(next<length&&nums[next]==-1) next++;
            if (next>length-1) nextNum = 1;
            else nextNum = nums[next];
            // Calculate the value of the current balloon coin
            int tempCoin = temp * nextNum * beforeNum;
            // Recursion for the next stamp 
            dfs(nums, y+1, length,beforeCoins+tempCoin,maxCoin);
            // Backtracking try other stamping methods 
            nums[i] = temp;
        }
    }

The first 1 Layer traversal n A balloon , The first 2 Layer traversal n-1 A balloon , The first 3 Layer traversal n-2 A balloon , A total of n!, Time complexity is very high , It will time out when submitting .

2、 Divide and conquer method + Memory search

Because the time complexity of ordinary depth first search is O(n!), We can use Divide and conquer thoughts To reduce the scale of the problem .

First, we try to puncture each balloon i, Take the balloon as the boundary to array the balloons [left,right] In two parts [left,i-1] and [i+1,right], Use the solutions of these two intervals to solve the original problem . Suppose the interval is punctured [left,right] The maximum number of gold coins a balloon can get coin=dfs(left,right), When we poke the balloon i when , The maximum values of the two intervals are dfs(left, i-1 ) And dfs( i+1 , right).

however Burst the balloon i when ,  The adjacency of the balloon array has changed ,i-1 And i+1 Originally all with i adjacent , and i After puncturing, the two of them were directly adjacent , And pierce it first i+1 And stab first i-1 The results will be completely different , That is to say, there is a dependency between the two subproblems . If you prick it first i-1 , be i+1 The adjacent balloon on the left becomes i-2; conversely i-1 The adjacent balloon on the right becomes i+2 . The processing order of the two subproblems will affect the solution of each subproblem .

Since both subproblems depend on i And two boundaries , Then we can redefine the way we divide ：

dfs(left,right) Indicates the punctured interval （left,right） The maximum number of gold coins a balloon can get （ Be careful ,left and right All balloons will be kept ）

So when you poke a balloon i when ,dfs(left,right)=dfs(left,i)+dfs(i,right)+x. here left、i、right The balloon hasn't burst yet .

We can add a value of... At the beginning and end of the original balloon array 1 The elements of , So let's start with the balloon array 0 and len-1 There is no need to poke the balloon in the position （ Because we joined it ourselves , There is no ）, We just need to prick the balloon i that will do , be x=nums[left]*nums[i]*[right].

In the above state transition equation , We need to search for balloons that try to puncture i,i The value of is obviously （left,right）, And we are going to take the largest gold coins , That is, when searching , Just save the maximum value . So the state transfer equation is ：

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

The implementation code is as follows ：

//  Method 2 ： Memory search 
    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);
    }
    //  Definition ： In the left open right open section （left,right） The maximum number of gold coins obtained by puncturing all balloons 
    int dfs(vector<int>& nums,int left,int right,vector<vector<int>>&dp){
        if(left==right-1) return 0;//  If the interval is empty , return 0
        if(dp[left][right]!=-1) return dp[left][right];//  If the interval has been searched , Go straight back to 
        int max_v=0;// 
        //  Try to puncture （left,right） No i A balloon 
        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、 Dynamic programming

Memory search and dynamic programming are basically two different versions of the same idea ： recursive and iteration .

【 State definition 】dp[left][right] Indicates the punctured interval （left,right） The maximum number of gold coins a balloon can get

【 State transition 】dp[left][right]=max(dp[left][right],dp[left][i]+dp[i][right]+nums[left]*nums[i]*[right]), among i The value is （left,right）

【 Initial state 】 According to the definition right>=left+1,left The value is [0,len-1]

int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        int len=nums.size();
        //dp[left][right]  Definition ： In the left open right open section （left,right） The maximum number of gold coins obtained by puncturing all balloons 
        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;
                //  Try to puncture （left,right） No i A balloon 
                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];
    }