本文共 4131 字，大约阅读时间需要 13 分钟。

有 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 = [1,5]

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];    }}

题源：

转载地址：https://blog.csdn.net/xxyneymar/article/details/122029209 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！