响应式网站建设策划,全球新冠最新数据报告,福州seo代理计费,一套完整的app 开发流程题目描述 这是 LeetCode 上的 「312. 戳气球」 #xff0c;难度为 「困难」。 Tag : 「区间 DP」、「动态规划」 有 n 个气球#xff0c;编号为 0 到 n - 1#xff0c;每个气球上都标有一个数字#xff0c;这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i … 题目描述 这是 LeetCode 上的 「312. 戳气球」 难度为 「困难」。 Tag : 「区间 DP」、「动态规划」 有 n 个气球编号为 0 到 n - 1每个气球上都标有一个数字这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和 i 相邻的两个气球的序号。 如果 i - 1 或 i 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 提示 区间 DP 定义 为考虑将 范围内不包含 l 和 r 边界的气球消耗掉所能取得的最大价值。 根据题意我们可以对 nums 进行扩充将其从长度为 的 nums 变为长度 的 arr其中 对应了原数组 nums而 。 此时易知 即是答案不失一般性考虑 该如何转移假设在 范围内最后剩下的气球的编号为 此时的 由「以 为分割点的两端所产生的价值」和「消耗 本身带来的价值」两部分组成 为了确保转移能够顺利进行我们需要确保在计算 的时候区间长度比其小的 和 均被计算。 因此我们可以采用先枚举区间长度 len然后枚举区间左端点 l同时直接算得区间右端点 r的方式来做。 Java 代码 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 代码 function maxCoins(nums: number[]): number { const n nums.length const arr new Arraynumber(n 2).fill(1) for (let i 1; i n; i) arr[i] nums[i - 1] const f new ArrayArraynumber(n 2) for (let i 0; i n 2; i) f[i] new Arraynumber(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]} 时间复杂度 空间复杂度 最后 这是我们「刷穿 LeetCode」系列文章的第 No.312 篇系列开始于 2021/01/01截止于起始日 LeetCode 上共有 1916 道题目部分是有锁题我们将先把所有不带锁的题目刷完。 在这个系列文章里面除了讲解解题思路以外还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 为了方便各位同学能够电脑上进行调试和提交代码我建立了相关的仓库https://github.com/SharingSource/LogicStack-LeetCode 。 在仓库地址里你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 本文由 mdnice 多平台发布
