312. Burst Balloons

calx 发布于2019-08-19 10:45 / 2488人阅读

摘要：接下来就是方程的问题了。首先肯定是要遍历切分点，然后找使最大的切分点，容易想到这个切分点表示的是扎破气球的位置。还有一种考虑的方式，就是说和不算在内。那么方程现在变成，并且取不到边界或者。

312. Burst Balloons

题目链接：https://leetcode.com/problems...

这题的dp方程还是挺难想的。首先subproblem比较容易：dp[i][j]: max coins I can get if there are balloons (i, j) left，有n^2个subproblem。接下来就是方程的问题了。

首先肯定是要遍历切分点：k，然后max找使coin最大的切分点，容易想到这个切分点表示的是扎破气球的位置。但是如果选择这个位置作为区间(i, j)里面第一次扎破气球的位置，问题就来了，扎破k之后，区间(i, j)内部需要合并，一个式子看起来是没法做的。所以转换一下思路，设k是区间内最后一个扎破的气球，那么问题就简单多了。k是区间内最后一个的话，k现在相邻的点就是i-1和j+1了，注意如果i = 0, j = n-1，要多带带讨论下，还有分割点可以取左右边界i或者j。

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        
        int[][] dp = new int[n][n];
        
        for(int len = 0; len < n; len++) {
            for(int i = 0; i < n - len; i++) {
                int j = i + len;
                for(int k = i; k <= j; k++) {
                    int l = i > 0 ? nums[i-1] : 1;
                    int r = j < n-1 ? nums[j+1] : 1;
                    int left = k - 1 >= i ? dp[i][k-1] : 0;
                    int right = k + 1 <= j ? dp[k+1][j] : 0;
                    dp[i][j] = Math.max(dp[i][j], l*nums[k]*r + left + right);
                }
            }
        }
        return dp[0][n-1];
    }
}

还有一种考虑subproblem的方式：dp[i][j]: : max coins I can get if there are balloons (i, j) left，就是说i和j不算在内。那么dp方程现在变成：dp[i][j] = max(nums[i]*nums[k]*nums[j], dp[i][k] + dp[k][j])，并且k取不到边界i或者j。这时候，base case结果就变了: dp[i][i] = 0, dp[i][i+1] = 0

参考discussion：
https://discuss.leetcode.com/...

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76402.html

[LeetCode] 312. Burst Balloons

Problem Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get...

TerryCai 2019-08-16 13:53 评论0 收藏0
leetcode 312. Burst Balloons

摘要：之后该气球将消失，从而其左右两个气球成为相邻的气球。这意味着的时间复杂度。这样就违背了分治法将问题分解为独立问题的要求。此时得到的子队列长度等于，因此将无法拆解，即结束。题目要求 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by arr...

pinecone 2019-08-15 14:49 评论0 收藏0
312. Burst Balloons

public class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] newNum = new int[n+2]; newNum[0] = 1; newNum[n+1] = 1; for(int i=0; i

wyk1184 2019-08-16 10:36 评论0 收藏0
css-in-js 探讨

摘要：库通过在中插入标签在运行时创建样式。结论是一体化的样式解决方案，用于弥合和之间的差距。零运行时解决方案通过恢复工具来缓解一些缺点，这些工具将讨论提升到更有趣的水平。 Web开发是需要掌握多种技术。我们习惯于与多种语言密切合作。而且，随着开发Web应用程序变得越来越普遍和差别细微化，我们经常寻找创造性的方法来弥合这些语言之间的差距，从而使我们的开发环境和工作流程更容易，更高效。最常见的...

Scliang 2019-08-30 15:54 评论0 收藏0
解析React SSR 中的限流案例

　　本篇文章主要为大家讲述关于ReactSSR之限流，其实我们都知道React SSR是涉及到服务端的，因此，我们先需要考虑到很多的服务器端问题，下面就为大家举例说明。　　当简单来说， React 的应用进行页面加载或 SEO 优化时，都会想到React SSR。也就会想到服务器端，这是必须考虑到的。　　现在我们来说下所谓限流，其实是在我们的服务资源有限、处理能力有限时，通过对请求或并发数进行限制...

3403771864 2023-03-17 08:28 评论0 收藏0