前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【区间 DP】热门区间 DP 运用题

【区间 DP】热门区间 DP 运用题

作者头像
宫水三叶的刷题日记
发布2023-10-25 19:03:41
1840
发布2023-10-25 19:03:41
举报

题目描述

这是 LeetCode 上的「312. 戳气球」,难度为「困难」

Tag : 「区间 DP」、「动态规划」

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

现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1i + 1 代表和 i 相邻的两个气球的序号。

如果 i - 1i + 1 超出了数组的边界,那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1:

代码语言:javascript
复制
输入: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:

代码语言:javascript
复制
输入:nums = [1,5]

输出:10

提示:

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

区间 DP

定义

f[l][r]

为考虑将

(l, r)

范围内(不包含 lr 边界)的气球消耗掉,所能取得的最大价值。

根据题意,我们可以对 nums 进行扩充,将其从长度为

n

nums 变为长度

n + 2

arr,其中

arr[1...n]

对应了原数组 nums,而

arr[0] = arr[n + 1] = 1

此时易知

f[0][n + 1]

即是答案,不失一般性考虑

f[l][r]

该如何转移,假设在

(l, r)

范围内最后剩下的气球的编号为

k

,此时的

f[l][r]

由「以

k

为分割点的两端所产生的价值」和「消耗

k

本身带来的价值」两部分组成:

f[l][r] = \max(f[l][k] + f[k][r] + arr[l] \times arr[k] \times arr[r]), k \in (l, r)

为了确保转移能够顺利进行,我们需要确保在计算

f[l][r]

的时候,区间长度比其小的

f[l][k]

f[k][r]

均被计算。

因此我们可以采用先枚举区间长度 len,然后枚举区间左端点 l(同时直接算得区间右端点 r)的方式来做。

Java 代码:

代码语言:javascript
复制
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n + 2];
        arr[0] = arr[n + 1] = 1;
        for (int i = 1; i <= n; i++) arr[i] = nums[i - 1];
        int[][] f = new int[n + 2][n + 2];
        for (int len = 3; len <= n + 2; len++) {
            for (int l = 0; l + len - 1 <= n + 1; l++) {
                int r = l + len - 1;
                for (int k = l + 1; k <= r - 1; k++) {
                    f[l][r] = Math.max(f[l][r], f[l][k] + f[k][r] + arr[l] * arr[k] * arr[r]);
                }
            }
        }
        return f[0][n + 1];
    }
}

TypeScript 代码:

代码语言:javascript
复制
function maxCoins(nums: number[]): number {
    const n = nums.length
    const arr = new Array<number>(n + 2).fill(1)
    for (let i = 1; i <= n; i++) arr[i] = nums[i - 1]
    const f = new Array<Array<number>>(n + 2)
    for (let i = 0; i < n + 2; i++) f[i] = new Array<number>(n + 2).fill(0)
    for (let len = 3; len <= n + 2; len++) {
        for (let l = 0; l + len - 1 <= n + 1; l++) {
            const r = l + len - 1
            for (let k = l + 1; k <= r - 1; k++) {
                f[l][r] = Math.max(f[l][r], f[l][k] + f[k][r] + arr[l] * arr[k] * arr[r])
            }
        }
    }
    return f[0][n + 1]
}
  • 时间复杂度:
O(n^3)
  • 空间复杂度:
O(n^2)
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2023-10-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 区间 DP
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档