网站建设保障方案,apicloud官网下载,万能应用商店下载安装,wordpress发布文章附件1. 题目
有 n 个气球#xff0c;编号为0 到 n-1#xff0c;每个气球上都标有一个数字#xff0c;这些数字存在数组 nums 中。
现在要求你戳破所有的气球。每当你戳破一个气球 i 时#xff0c;你可以获得 nums[left]∗nums[i]∗nums[right]nums[left] * nums[i] * nums[ri…1. 题目
有 n 个气球编号为0 到 n-1每个气球上都标有一个数字这些数字存在数组 nums 中。
现在要求你戳破所有的气球。每当你戳破一个气球 i 时你可以获得 nums[left]∗nums[i]∗nums[right]nums[left] * nums[i] * nums[right]nums[left]∗nums[i]∗nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
你可以假设 nums[-1] nums[n] 1但注意它们不是真实存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:输入: [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来源力扣LeetCode 链接https://leetcode-cn.com/problems/burst-balloons 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. DP解题
看的别人的解题思路
dp[i][j]dp[i][j]dp[i][j] 表示戳破 i 到 j 的气球获得的最大金币每次戳破气球的顺序会影响后面的结果直接求解的复杂度是O(n!)O(n!)O(n!)逆向思考假设最后戳破 k 号气球那么 k 号气球左边和右边的求解是互不干扰的dp[i][j]max(dp[i][j],dp[i][k−1]nums[i−1]∗nums[k]∗nums[j1]dp[k1][j])dp[i][j] max(dp[i][j],\quad dp[i][k-1]nums[i-1]*nums[k]*nums[j1]dp[k1][j])dp[i][j]max(dp[i][j],dp[i][k−1]nums[i−1]∗nums[k]∗nums[j1]dp[k1][j])[i,j][i,j][i,j] 有多少种组合呢用他们的长度 lenlenlen 表示 1lenn1lenn1lenn在长度len下ij 窗口遍历数组在 ij 窗口内用递推公式求 dp[i][j]dp[i][j]dp[i][j]
class Solution {
public:int maxCoins(vectorint nums) {int n nums.size();nums.insert(nums.begin(),1);//首尾加入虚拟的气球nums.push_back(1);vectorvectorint dp(n2,vectorint(n2,0));int len, i, j, k;for(len 1; len n; len) {for(i 1; i n-len1; i){j leni-1;for(k i; k j; k){dp[i][j]
max(dp[i][j],dp[i][k-1]dp[k1][j]nums[i-1]*nums[k]*nums[j1]);}}}return dp[1][n];}
};
