(nice!!!)LeetCode 312. 戳气球（区间dp ||记忆化dfs ）

312. 戳气球

思路：经典区间dp问题。方法一，区间dp。状态dp[i][j]表示：i_{j这个区间能获得的最大硬币数量。那么我们就可以枚举区间i}j的每一个点，为该区间最后一个戳破的气球。细节看注释

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        //状态dp[i][j]表示：i~j这个区间能获得的最大硬币数量
        vector<vector<int>> dp(n,vector<int>(n,0));
        //从小到大枚举区间的长度
        for(int lens=1;lens<=n;lens++){
        	//枚举区间的左端点
            for(int i=0;i+lens<=n;i++){
            	//区间的右端点（实际是j-1）
                int j=i+lens;
                //把这个区间i~j外边的气球找出来
                int t=1;
                if(i!=0) t*=nums[i-1];
                if(j!=n) t*=nums[j];
                //枚举区间i~j的每一个点，为该区间最后一个戳破的气球
                for(int k=i;k<j;k++){
                	//计算出最后一个点被搓破前，获得的最大硬币数量。
                    int tmp=0;
                    if(k!=i) tmp+=dp[i][k-1];
                    if(k!=j-1) tmp+=dp[k+1][j-1];
                    //更新区间i~j的最大硬币数量
                    dp[i][j-1]=max(dp[i][j-1],t*nums[k]+tmp);
                }
            }
        }
        //答案自然就是0~n-1这个区间啦
        return dp[0][n-1];
    }
};

思路：方法二，记忆化dfs。区间dp都能做的题，记忆化dfs当然也可以！思路和方法一一样，记忆化dfs的好处就是只需要知道最后一步是干什么的，就可以啦！细节看注释

class Solution {
public:
    int n;
    vector<vector<int>> dp;
    //l:区间左端点、r:区间右端点
    int dfs(int l,int r,vector<int>& nums){
        //if(l>r) return dp[l][r]=0;
        //这里就是记忆化啦，避免大量的重复计算
        if(dp[l][r]!=-1) return dp[l][r];
        //把这个区间l~r外边的气球找出来
        int t=1;
        if(l!=0) t*=nums[l-1];
        if(r!=n-1) t*=nums[r+1];
        //枚举区间l~r的每一个点，为该区间最后一个戳破的气球
        for(int i=l;i<=r;i++){
        	//计算出最后一个点被搓破前，获得的最大硬币数量。
            int tmp=0;
            if(i!=l) tmp+=dfs(l,i-1,nums);
            if(i!=r) tmp+=dfs(i+1,r,nums);
            //更新区间i~j的最大硬币数量
            dp[l][r]=max(dp[l][r],tmp+t*nums[i]);
        }
        return dp[l][r];
    }
    int maxCoins(vector<int>& nums) {
        n=nums.size();
        dp=vector<vector<int>>(n,vector<int>(n,-1));
        
        dfs(0,n-1,nums);
        return dp[0][n-1];
    }
};