跳至主要內容

 

labuladong原创动态规划约 2834 字大约 9 分钟

Info

新版网站会员open in new window 限时优惠;算法可视化编辑器上线,点击体验open in new window

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
312. Burst Balloonsopen in new window312. 戳气球open in new window🔴

今天我们要聊的这道题「Burst Balloon」和之前我们写过的那篇 经典动态规划:高楼扔鸡蛋问题 分析过的高楼扔鸡蛋问题类似,知名度很高,但难度确实也很大。因此我的公众号就给这道题赐个座,来看一看这道题目到底有多难。

它是力扣第 312 题「戳气球open in new window」,题目如下:

312. 戳气球 | 力扣 open in new window | LeetCode open in new window |

n 个气球,编号为0n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1i + 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 <= 300
  • 0 <= nums[i] <= 100

首先必须要说明,这个题目的状态转移方程真的比较巧妙,所以说如果你看了题目之后完全没有思路恰恰是正常的。虽然最优答案不容易想出来,但基本的思路分析是我们应该力求做到的。所以本文会先分析一下常规思路,然后再引入动态规划解法。

一、回溯思路

先来顺一下解决这种问题的套路:

加载中...

上次编辑于: