做招聘网站需要哪些手续,如何购买域名和服务器,网页设计培训好学吗,广州白云区网站建设公司#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 动态规划 求解思路 实现代码 运行结果 共勉 题目链接
312. 戳气球
⛲ 题目描述
有 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 315 358 138 181 167 示例 2
输入nums [1,5] 输出10
提示
n nums.length 1 n 300 0 nums[i] 100 求解思路实现代码运行结果 ⚡ 动态规划 求解思路
dp[i][j]表示第i至第j个元素这个区间能获得的最大硬币数k表示在i,j这个区间内最后戳破的气球状态转移方程dp[i][j]max(dp[i][j],dp[i][k]dp[k][j]nums[i]*nums[k]*nums[j])。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class Solution {public int maxCoins(int[] nums) {if(nums null || nums.length 0) {return 0;}int n nums.length;//创建一个n2的数组开头和末尾都填1int[] arr new int[n 2];for(int i 1; i n; i) {arr[i] nums[i - 1];}arr[0] 1;arr[n 1] 1;int[][] dp new int[n 2][n 2];//从下往上遍历i控制左边界j控制右边界for(int i n - 1; i 0; --i) {for(int j i 2; j n 1; j) {//k在(i,j)范围内遍历气球计算每选择一个气球的积分//一轮遍历完后就能确定(i,j)的最大积分for(int k i 1; k j; k) {int total arr[i] * arr[k] * arr[j];total dp[i][k] dp[k][j];dp[i][j] Math.max(dp[i][j], total);}}}return dp[0][n 1];}
} 运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
