网站的企业风采怎么做,wordpress创建数据库文件,南京网站开发南京乐识权威,感谢使用wordpress进行创作有 n 个气球#xff0c;编号为0 到 n - 1#xff0c;每个气球上都标有一个数字#xff0c;这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球#xff0c;你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和 i 相邻…有 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提示 ·n nums.length ·1 n 300 ·0 nums[i] 100
题目大意在戳破一个气球可获得该气球与周围气球乘积数的情况下计算最多可获得的乘积数。
分析
1在戳破一个气球后会造成不相邻的气球变得相邻较难处理因此考虑反向操作。将题目过程改为从两个数字为1的气球中不断插入气球每次插入可获得插入球与相邻球的乘积数计算最多可获得的乘积数
2通过1中方法将问题转换为插入气球的问题由于是从两个数字为1的气球开始插入因此在nums数组的首尾插入数字1再设dp[l][r]为在区间lr中的气球全部插满最多可获得的硬币数。若区间lr中第一个气球插入的位置为midlmidr则dp[l][r]dp[l][mid]dp[mid][r]nums[l]*nums[mid]*nums[r]。由此计算方式可得状态转移方程 class Solution {
public:int maxCoins(vectorint nums) {nums.insert(nums.begin(),1);nums.emplace_back(1);int Nnums.size();vectorvectorint dp(N,vectorint(N,0));for(int len2,l,r,mid;lenN;len){for(l0,rllen;rN;l,r){for(midl1;midr;mid){dp[l][r]max(dp[l][r],dp[l][mid]dp[mid][r]nums[l]*nums[mid]*nums[r]);}}}return dp[0][N-1];}
};
