力扣题312戳气球_有 n个气球,编号为1到n,每个气球上都标有一个数字,用数组balls来存储这些数字。

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 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
示例 2：

输入：nums = [1,5]
输出：10

1.自己的解法：想用回溯法，把每种和都计算出来，然后取最大值。

        这种方法可以通过测试用例，但是提交后显示超出时间限制。因为使用这种回溯法，会造成

      大量的重复计算。

class Solution {
    int maxCount = 0;//记录最大值
 
    public int maxCoins(int[] nums) {
        boolean[] isVisited = new boolean[nums.length];//存储每个气球的状态，是否被戳破
        maxCoins(nums,isVisited,0,0);
 
        return maxCount;
    }
 
    public void maxCoins(int[] nums,boolean[] isVisited,int curCount,int length) {
        if (length == nums.length) {//所有气球都被戳皮后，比较是否需要更新最大值
            maxCount = Math.max(maxCount,curCount);
            return;
        }
 
        for (int i = 0;i < nums.length;i++) {//遍历每种情况
            int curNum = curNum(nums,isVisited,i);//计算当前气球被戳破的话可以得到多少硬币
            if (!isVisited[i]) {//如果当前气球没有被戳破过
                curCount += curNum;//加上硬币数
                isVisited[i] = true;//更新气球状态
                maxCoins(nums,isVisited,curCount,length + 1);
            } else{//如果当前气球被戳破了，直接跳过
                continue;
            }
            //回溯
            isVisited[i] = false;
            curCount -= curNum;
        }
    }
    //该函数用来计算每个气球被戳破的话能够得到多少硬币
    public int curNum(int[] nums,boolean[] isVisited,int index) {
        int left = index - 1;
        int right = index + 1;
 
        while (left >= 0 && isVisited[left]) {//找到左侧第距离最近的未被戳破的气球
            left--;
            if (left < 0) {
                break;
            }
        }
 
        while (right <= nums.length - 1 && isVisited[right]) {//找到右侧距离最近的未被戳破的气球
            right++;
            if (right > nums.length - 1) {
                break;
            }
        }
 
        if (left < 0 && right > nums.length - 1) {//左右不存在未戳破的气球的情况
            return 1 * nums[index] * 1;
        } else if (left < 0) {//只有左侧气球被戳破的情况
            return 1 * nums[index] * nums[right];
        } else if (right > nums.length - 1) {//只有右侧气球被戳破的情况
            return nums[left] * nums[index] * 1;
        } else {//两侧气球均未被戳破的情况
            return nums[left] * nums[index] * nums[right];
        }
    }
}

2.题解：为了方便处理，我们对nums数组稍作处理，将其两边各加上题目中假设存在的 nums[−1] 和nums[n] ，并保存在val 数组中，即]val[i]=nums[i−1] 。之所以这样处理是为了处理nums[−1] ，防止下标越界。

        记忆化搜索：

class Solution {
    public int[][] rec;//存储每个区间的最大值
    public int[] val;//存储每个气球值
 
    public int maxCoins(int[] nums) {
        int n = nums.length;
        val = new int[n + 2];
        val[0] = val[n + 1] = 1;//在开头和末尾各自加上一个1，方便计算
        for (int i = 1;i <= n;i++) {
            val[i] = nums[i - 1];
        }
 
        rec = new int[n+2][n+2];
        for (int i = 0;i <= n + 1;i++) {
            Arrays.fill(rec[i],-1);
        }
 
        return solve(0,n+1);
    }
 
    public int solve(int left,int right) {
        if (left >= right - 1) {//表示所有气球都被戳完了
            return 0;
        }
 
        if (rec[left][right] != -1) { // 这个区间的最大值之前已经计算过了，直接返回，避免重复计算
            return rec[left][right];
        }
 
        for (int i = left + 1;i < right;i++) {
            int sum = val[left] * val[i] * val[right];//当前气球被戳破的到的硬币数
            sum += solve(left,i) + solve(i,right);//递归计算左侧最大和与右侧最大和
            rec[left][right] = Math.max(rec[left][right],sum);//更新当前区间的最大值
        }
        return rec[left][right];
    }
}

        动态规划：

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] val = new int[n + 2];
        val[0] = val[n + 1] = 1;//在开头和末尾各自加上一个1，方便计算
        for (int i = 1;i <= n;i++) {
            val[i] = nums[i - 1];
        }
 
        int[][] rec = new int[n+2][n+2]; //开区间
        //i从末端开始，为了从小区间得到大区间
        for (int i = n - 1;i >= 0;i--) {//开区间左侧起点
            for (int j = i + 2;j <= n + 1;j++) {//右侧中点
                for (int k = i + 1;k < j;k++) {//这个开区间的中间值
                    int sum = val[i] * val[k] * val[j];
                    sum += rec[i][k] + rec[k][j];
                    rec[i][j] = Math.max(rec[i][j],sum);
                }
            }
        }
        return rec[0][n + 1];
    }
}

题源：力扣