312. 戳气球 (opens new window)

1.记忆化搜索+枚举+动规(子问题)

分析：算法本质是通过暴力枚举，选出得分最高的结果。

• 规定左右边界的气球不戳破，用于计算戳破最后一个气球的得分，假设最后戳破的气球为第i个气球，那么戳破所有【left,right】之间所有气球的得分计算公式为：

  currScore=nums[left]*nums[i]*nums[right]+戳破【left,i】所有气球的得分+戳破【i,right】所有气球的得分。

  • 从后往前思考：这里戳破一个区间的所有气球的总得分，先考虑最后一个气球，最后慢慢缩小区间长度转化为子问题。因为如果从前往后思考，枚举当前区间的第一个戳破的气球，那么计算下一个气球戳破时的得分，①不仅需要保存每个气球的使用位②还需要保存当前这个气球戳破时相邻的左右元素，流程繁琐③更致命的，从前向后枚举没有利用到子问题的解，因此导致超时，时间复杂度为n*(n-1)*(n-2)...
  • 那么问题来了，最后一个戳破气球的搜索策略是什么？如果每次选择左右区间内的最大值作为最后一个区间戳破的气球，最终结果是错的。只能通过枚举所有可能的最后一个戳破气球的结果，选择分数最高的结果作为区间值。

• 开辟一个二维数组保存搜索过的子问题的解，从而降低枚举搜索时的时间复杂度。复杂度为O(n三次方)，其中n平方为总共的区间数(状态数)，每个区间的最大分数求解时需要枚举n次。

• ✨核心是将问题转化子问题，利用分支归并的思想。并且逆向思考是搜索过程中破局的关键。

class Solution {
    int[][] dfs;
    public int maxCoins(int[] nums) {
        dfs=new int[nums.length+2][nums.length+2];
        return find(nums,0,nums.length+1);
    }
    public int find(int[] nums,int start,int end){
        if(start+1==end) return 0;
        int left=start==0?1:nums[start-1];
        int right=end==nums.length+1?1:nums[end-1];
        int max=Integer.MIN_VALUE,index=start+1;
        for(int i=start+1;i<=end-1;i++){
            int lsum=dfs[start][i]==0?find(nums,start,i):dfs[start][i];
            int rsum=dfs[i][end]==0?find(nums,i,end):dfs[i][end];
            max=Math.max(max,nums[i-1]*left*right+lsum+rsum);
        }
        dfs[start][end]=max;
        return max;
    }
}