经典动态规划：戳气球 :: labuladong的算法小抄

[labuladong]

文章链接点这里：经典动态规划：戳气球

评论礼仪 见这里，违者直接拉黑。

[Goolloo]

DFS ver.

class Solution {
    public int maxCoins(int[] nums) {
        int size = nums.length + 2;
        int[] points = new int[size];
        points[0] = 1;
        points[size-1] = 1;
        for(int i = 0; i < nums.length; i++) {
            points[i+1] = nums[i];
        }
        
        int[][] memo = new int[size][size];
        
        int result = dp(points, memo, 0, size-1);
        
        // Arrays.stream(memo).map(Arrays::toString).forEach(System.out::println);
        
        return result;
    }
    
    private int dp(int[] points, int[][] memo, int left, int right) {
        // base case
        if(left + 1 == right) {
            return 0;
        }
        
        // continue
        
        // memo check
        if(memo[left][right] > 0) {
            return memo[left][right];
        }
        
        // find max
        int max = 0;
        int pointsBase = points[left] * points[right];
        for(int i = left + 1; i < right; i++) {
            max = Math.max(
                max, 
                points[i] * pointsBase 
                + dp(points, memo, left, i) 
                + dp(points, memo, i, right)
            );
        }
        memo[left][right] = max;
        return max;
    }
}

[ZYunfeii]

没超时么

[ZYunfeii]

懂了 我用map当memo，C++里面用了to_string，有点耗时..

[GoingMyWay]

这个dfs带memo的比较好理解一些。

[cjxiee]

既然dp[i][j]的定义是(i,j)开区间上的最大值，为什么不可以通过比较（i+1,j）区间的最大值加上戳破i+1得到的值和（i,j-1）区间的最大值加上戳破j-1得到的值来推算出dp[i][j]的值？

[lpdswing]

请问i为什么是 n -> 0遍历呢, 我试了 n+2 -> 0也是ok的

[GoingMyWay]

看了文章，还是不太懂为什么i的遍历规则是n->0，为啥不是0->n。

[GoingMyWay]

摘抄自leetcode.cn

/**
 * dp版本代码，最外层的循环，i为什么是n-1 -> 0，而不能反过来？
 * (i,j) 0 1  2   3   4   ...   n-2   n-1   n   n+1
 * 0     0 1  2   3   4   ...                   n+1
 * 1       1  2   3   4   ...                   n+1
 * 2          2   3   4   ...                   n+1
 * 3              3   4   ...                   n+1
 * 4                  4                         n+1
 * .                      .                     .
 * .                         .                  .
 * n-2                          n-2   n-1   n   n+1
 * n-1                                n-1   n   n+1
 * n+1
 *
 * 须从下往上算，即先算dp[n-1][n+1]：
 * 根据递推关系，算dp[i][j]时依赖的dp[i][k]和dp[k][j]，其中i<k<j。
 * 1、如果从上往下计算，依赖的dp[k][j]根本就还未算出（k比i大），比如算dp[0][3]时，依赖的dp[1][3]还是个未知数。
 * 2、从下往上就不一样，算dp[i][j]时，依赖的dp[i][k]，位于同一行左侧，已计算过；
 *                                    依赖的dp[k][j]，因为k>i，位于更下面的行，也已计算过。
 */

[Matilda-Yxx]

Py3 version:

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        
        n = len(nums)
        ballons = [1]+nums+[1]
        dp = [[0]*(n+2) for _ in range(n+2)]
        
        for i in range(n, -1, -1):
            for j in range(i+1, n+2, 1):
                res = 0
                for k in range(i+1, j):
                    res = max(res, dp[i][k] + dp[k][j] + ballons[i] * ballons[k] * ballons[j])
                dp[i][j] = res
            
        return dp[0][n+1]

[EyeDroplyq]

打卡

[EyeDroplyq]

附上代码，有详细注释

    //这是一个求最值的问题，所以我们考虑使用动态规划来解决这个问题
    public int maxCoins(int[] nums) {
        int n=nums.length;
        //为什么用n+2呢？意思就是把最左边和最右边这两个实际上没有的气球加进来，是模拟的气球
        int[] points=new int[n+2];
        //因为虚拟气球的值为1，所以我们给它进行赋值
        points[0]=points[n+1]=1;
        for (int i = 1; i <=n ; i++) {
            points[i]=nums[i-1];
        }
        //上面的步骤完成之后，我们的这个points数组中就是我们的所有的气球的值，包括我们自己加的两个虚拟气球

        //dp 数组的定义：dp[i][j]表示戳破（i,j）之间的气球可以得到的最大金币，注意是开区间，左右两端是不会戳破的
        int[][] dp=new int[n+2][n+2];

        //base case:当j<i的时候，肯定是不合法的，所以dp数组此时为0
        //虽然这个base case可以省略的，但是写在这里更加好理解点
        for (int i = 0; i < n + 2; i++) {
            for (int j = 0; j < i; j++) {
                dp[i][j]=0;
            }
        }
        //状态转移：当最后戳破的气球是k这个位置的气球的话，我们可以获得的最多的金币是，dp[i][k]+dp[k][j]+points[i]*points[k]*points[j]
        //意思就是戳完左边的最大金币+戳破右边气球的最大金币+最后这个戳破气球的金币

        //遍历的方向，一般就是从base case出发。然后向最后结果靠拢
        for (int i = n; i >=0 ; i--) {
            for (int j = i+1; j <n+2 ; j++) {
                //k就是最后戳破的气球的位置，k肯定是在i和j之间的
                for (int k = i+1; k <j ; k++) {
                    dp[i][j]=Math.max(dp[i][j],dp[i][k]+dp[k][j]+points[i]*points[k]*points[j]);
                }
            }
        }
        return dp[0][n+1];
    }