LeetCode_每日一题今日份_312.戳气球（没懂）

向右看齐 2023-02-28 04:21 120阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]  
题解Java

class Solution {
        
        public int[][] rec;
        public int[] val;
    
        public int maxCoins(int[] nums) {
        
            int n = nums.length;
            val = new int[n + 2];
            for (int i = 1; i <= n; i++) {
        
                val[i] = nums[i - 1];
            }
            val[0] = val[n + 1] = 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];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: /images/20230209/f29effd7e03f459f891fab264b123fc3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode452. 用最少数量的箭引爆气球（20201123每日一题）

解题思路：贪心算法（思想），排序+找最大交集 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9i

桃扇骨/ 2023年10月09日 13:22/ 0 赞/ 12 阅读

相关 312. 戳气球（动态规划）

312. 戳气球题目解题思路代码题目有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中

向右看齐/ 2023年10月05日 19:41/ 0 赞/ 21 阅读

相关 LeetCode.每日一题今日份_392.判断子序列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

逃离我推掉我的手/ 2023年03月01日 13:50/ 0 赞/ 28 阅读

相关 LeetCode_每日一题今日份_167.两数之和II-输入有序数组

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

秒速五厘米/ 2023年02月28日 11:12/ 0 赞/ 8 阅读

相关 312. 戳气球

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums\[le

以你之姓@/ 2023年02月28日 05:44/ 0 赞/ 55 阅读

相关 LeetCode_每日一题今日份_312.戳气球（没懂）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

向右看齐/ 2023年02月28日 04:21/ 0 赞/ 121 阅读

相关 312戳气球

一、前言分类：动态规划。问题来源LeetCode 312 难度：困难。问题链接：[https://leetcode-cn.com/problems/burst-

向右看齐/ 2023年02月24日 01:32/ 0 赞/ 15 阅读

相关【LeetCode-每日一题】-739-每日温度

1. 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

梦里梦外;/ 2023年02月20日 02:15/ 0 赞/ 29 阅读

相关 LeetCode 312. 戳气球

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

骑猪看日落/ 2022年10月29日 05:17/ 0 赞/ 169 阅读

相关 LeetCode312——戳气球

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

忘是亡心i/ 2022年01月23日 10:05/ 0 赞/ 236 阅读