lintcode 168. 吹气球【记忆化搜索+区间dp】-北京尧图网络

168. 吹气球中文English有n个气球编号为0到n-1每个气球都有一个分数存在nums数组中。每次吹气球i可以得到的分数为nums[left] * nums[i] * nums[right]left和right分别表示i气球相邻的两个气球。当i气球被吹爆后其左右两气球即为相邻。要求吹爆所有气球得到最多的分数。样例样例 1:输入[4, 1, 5, 10] 输出270 解释 nums [4, 1, 5, 10] 吹爆 1, 得分 4 * 1 * 5 20 nums [4, 5, 10] 吹爆 5, 得分 4 * 5 * 10 200 nums [4, 10] 吹爆 4, 得分 1 * 4 * 10 40 nums [10] 吹爆 10, 得分 1 * 10 * 1 10 总得分 20 200 40 10 270样例 2:输入[3,1,5] 输出35 解释 nums [3, 1, 5] 吹爆 1, 得分 3 * 1 * 5 15 nums [3, 5] 吹爆 3, 得分 1 * 3 * 5 15 nums [5] 吹爆 5, 得分 1 * 5 * 1 5 总得分 15 15 5 35注意事项你可以假设nums[-1] nums[n] 1。-1和n位置上的气球不真实存在因此不能吹爆它们。0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100这个题告诉我们欠的技术宅早晚要还区间dp基础题放在面试里面都算是难的了for循环里面是遍历某一个点这个点是最后打的气球所以dp[x][y]dp[x][i-1] dp[i1][y] left*right*nums[i]注意的是 flag要在for循环后面因为for结束了才是当前区间遍历完class Solution { public: /** * param nums: A list of integer * return: An integer, maximum coins */ int dfs (int x, int y, vectorint nums, vectorvectorint dp, vectorvectorbool flag) { if (flag[x][y]) { return dp[x][y]; } int res 0; for (int i x; i y; i ) { dfs(x, i-1,nums,dp,flag); dfs(i1, y,nums,dp,flag); int left nums[x-1], right nums[y1]; res max(res, dp[x][i-1] dp[i1][y] left*right*nums[i]); } dp[x][y] res; flag[x][y] true; return dp[x][y]; } int maxCoins(vectorint nums) { // write your code here int n nums.size(); if (n 1) { return 0; } nums.insert(nums.begin(), 1); nums.push_back(1); vectorvectorintdp(n2,vectorint(n2,1)); vectorvectorboolflag(n2,vectorbool(n2,false)); return dfs(1,n,nums,dp,flag); } };

lintcode 168. 吹气球【记忆化搜索+区间dp】

相关推荐

Dify入门指南：从账号开通到界面核心功能详解

物联网设备安全芯片SE050与MCU集成方案解析

NBM7100A与STM32F030RC的低功耗物联网电源管理方案

更多资讯

git reset --hard 后悔药：用 reflog 和 fsck 找回丢失的代码

计算机专业生涯规划书：从Word文档到可验证技能路线图

Swift运算符速查清单：基础、位运算与自定义运算符全解析（Swift编程语言中文版）

OpenBCI脑电数据导入MNE：从CSV到脑地形图全流程

2026年AI编程工具全景：33款主流工具分类与实战选型指南

工业相机镜头选型全解析：从焦距计算到现场踩坑避雷指南

今日更新

AReaL 调试指南：从 Agent Workflow 验证到分布式训练死锁诊断

MATLAB实现GPS L1 C/A信号仿真与二维捕获验证

彻底搞懂ASCII、Unicode与UTF-8：从乱码根源到编码实战

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？