557，动态规划解戳气球

Original 博哥数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

Any mind that is capable of a real sorrow is capable of good.

真正悲伤过的人都是心存善念的。

问题描述

来源：LeetCode第312题

难度：困难

有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

提示：

n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100

递归解决

一般情况下我们会考虑到每一种可能的结果，然后计算他们的值，最后保留最大的即可，因为可选择的结果很多，下图只画出了最大的那个分支，来看下

比如上图中3和5本来是不相邻的，但当我们戳破1的时候，3和5变成了相邻，所以我们可以使用一个list把每个气球的值都存起来，戳破的时候就把他从list中给删除。来看下代码

 1public int maxCoins(int[] nums) {
 2    List<Integer> list = new LinkedList<>();
 3    //先把nums数组中的元素放到list中
 4    for (int num : nums) {
 5        list.add(num);
 6    }
 7    return helper(list);
 8}
 9
10public int helper(List<Integer> list) {
11    //如果是空，则表示没有气球了，直接返回0
12    if (list.isEmpty())
13        return 0;
14    int max = 0;
15    int size = list.size();
16    for (int i = 0; i < size; ++i) {
17        //戳破当前气球所获得的硬币数量
18        int sum = 0;
19        if (size == 1) {
20            //如果只有一个气球，直接戳破他获取的硬币就是
21            //当前气球上的数字
22            sum = list.get(i);
23        } else if (size == 2) {
24            //如果有两个气球，戳破任何一个气球都是他俩的乘积
25            sum = list.get(0) * list.get(1);
26        } else {
27            //如果是3个和3个以上的气球要注意戳破第1个和最后一个气球
28            //的边界条件
29            if (i == 0) {
30                sum = list.get(i) * list.get(i + 1);
31            } else if (i == size - 1) {
32                sum = list.get(i) * list.get(i - 1);
33            } else {
34                sum = list.get(i - 1) * list.get(i) * list.get(i + 1);
35            }
36        }
37        //把当前气球戳破了，就把他从list中移除
38        Integer num = list.remove(i);
39        //记录最大的值，sum表示戳破当前气球所得到的硬币数，
40        //helper(list)表示戳破剩下的气球所获得的硬币数
41        max = Math.max(max, sum + helper(list));
42        //把当前气球添加进list，尝试戳破下一个气球
43        list.add(i, num);
44    }
45    return max;
46}

当数据量比较大的时候，上面代码很容易超时。我们来换一种解法，定义函数helper(left,right)表示戳破开区间(left,right)中的所有气球所获得的最大硬币数。这里之所以定义开区间是因为我们戳破区间(left,right)中的任何气球都能找到两边的气球。假如是闭区间[left,right]，当我们戳破两边的气球的时候我们是不知道前面一个或者后面一个气球的值。

因为是开区间，当left+1>=right的时候，区间内是没有气球的。这里为了方便计算，我们来申请一个比原来数组长度大2的临时数组，临时数组的第1个和最后一个元素都是1。来看下代码

 1public int maxCoins(int[] nums) {
 2    int length = nums.length;
 3    //申请一个比原来长度大2的临时数组
 4    int[] temp = new int[length + 2];
 5    //临时数组的首尾值赋为1，中间的值和nums的值一样
 6    for (int i = 1; i <= length; i++)
 7        temp[i] = nums[i - 1];
 8    temp[0] = temp[length + 1] = 1;
 9    return helper(temp, 0, length + 1);
10}
11
12//戳破开区间(left,right)中所有气球所获得的最大硬币
13public int helper(int[] temp, int left, int right) {
14    //如果(left，right)之间没有气球，返回0，表示没有任何气球可戳破
15    if (left + 1 == right)
16        return 0;
17    int res = 0;
18    //在(left，right)中我们尝试戳破每一个位置的气球，取最大值即可
19    for (int i = left + 1; i < right; ++i) {
20        int sum = temp[left] * temp[i] * temp[right] + helper(temp, left, i) + helper(temp, i, right);
21        res = Math.max(res, sum);
22    }
23    return res;
24}

这样当数据量比较大的时候还是会超时，因为这里包含了大量的重复计算，我们还可以使用一个map，把计算的结果存到map中，下次使用的时候如果计算过了，就直接从map中取，来看下代码

 1public int maxCoins(int[] nums) {
 2    int length = nums.length;
 3    //申请一个比原来长度大2的临时数组
 4    int[] temp = new int[length + 2];
 5    //临时数组的首尾值赋为1，中间的值和nums的值一样
 6    for (int i = 1; i <= length; i++)
 7        temp[i] = nums[i - 1];
 8    temp[0] = temp[length + 1] = 1;
 9    int[][] map = new int[length + 2][length + 2];
10    return helper(map, temp, 0, length + 1);
11}
12
13public int helper(int[][] map, int[] temp, int left, int right) {
14    //如果(left，right)之间没有气球，返回0，表示没有任何气球可戳破
15    if (left + 1 == right)
16        return 0;
17    //如果已经计算过了，就直接从map中取
18    if (map[left][right] > 0)
19        return map[left][right];
20    int res = 0;
21    for (int i = left + 1; i < right; ++i) {
22        int sum = temp[left] * temp[i] * temp[right] + helper(map, temp, left, i) + helper(map, temp, i, right);
23        res = Math.max(res, sum);
24    }
25    //把计算的结果在存储到map中
26    map[left][right] = res;
27    return res;
28}

动态规划解决

我们定义dp[i][j]表示戳破开区间(i,j)中所有气球所获得的最大硬币，为了方便计算我们还是来申请一个临时数组，他的长度比原数组长度大2，那么这题就可以变成求戳破开区间(0,length+1)中所有气球所获得的最大硬币数，像下面这样

1    for (int i = length - 1; i >= 0; i--) {
2        for (int j = i + 2; j <= length + 1; j++) {
3            //计算戳破开区间(i,j)中间的气球所获取的最大硬币数
4           ……
5        }
6    }

如果一个气球被戳破后，本来不挨着的两个气球可能变成挨着的了，这样还是不好计算。我们可以这样来计算，在开区间(i,j)中随便找一个气球，假如是k，我们让k成为最后一个被戳破的气球，那么这样就简单了，当我们戳破气球k的时候所获得的最大硬币是

nums[i]*nums[k]*nums[j];

如下图所示

这个k可以是开区间(i,j)中的任何一个气球，取最大的即可，所以我们可以找出递推公式，在开区间(i,j)中戳破第k个气球所获得硬币数

sum=temp[i]*temp[k]*temp[j]+dp[i][k]+dp[k][j];

其中dp[i][k]表示戳破开区间(i,k)中的气球所获得的最大硬币数量，同理dp[k][j]，来看下代码

 1public int maxCoins(int[] nums) {
 2    int length = nums.length;
 3    //申请一个比原来长度大2的临时数组
 4    int[] temp = new int[length + 2];
 5    //临时数组的首尾值赋为1，中间的值和nums的值一样
 6    for (int i = 1; i <= length; i++)
 7        temp[i] = nums[i - 1];
 8    temp[0] = temp[length + 1] = 1;
 9    //dp[i][j]表示戳破开区间(i,j)之间的气球所获得的最大硬币数
10    int[][] dp = new int[length + 2][length + 2];
11    for (int i = length - 1; i >= 0; i--) {
12        for (int j = i + 2; j <= length + 1; j++) {
13            //遍历开区间(i,j)中的每一个气球，尝试戳破他所获得的最大硬币
14            for (int k = i + 1; k < j; k++) {
15                //递推公式，戳破气球k可以获得temp[i] * temp[k] * temp[j]个硬币，
16                //dp[i][k]表示戳破开区间(i,k)之间的气球所获得的硬币数
17                //dp[k][j]表示戳破开区间(k,j)之间的气球所获得的硬币数
18                int sum = temp[i] * temp[k] * temp[j] + dp[i][k] + dp[k][j];
19                //保留最大的
20                dp[i][j] = Math.max(dp[i][j], sum);
21            }
22        }
23    }
24    return dp[0][length + 1];
25}