312. 戳气球(C++)---动态规划解题_c++气球问题解答免费复制

题目详情

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 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

——题目难度:困难

分析

这道题使用动态规划的难点在于找准状态 和 怎么化为子问题。使用动态规划 子问题要必须独立。我的理解是一旦子问题完成了，其(最佳)状态确定了，再下一个子问题中就不能改动上一个子问题的状态了。就如174. 地下城游戏(C++)---动态规划(倒推)解题的正推时的感觉差不多，不能因为到达 (i, j) 发现之前最优路径的方案可以改变。

看了大佬的想法后知道了可以用如果要用dp数组时，先要改变下问题。题目说可以认为 nums[-1] = nums[n] = 1，那么可以先直接把这两个边界加进去，形成一个新的数组 val。现在气球的索引变成了从 1 到 n，val[0] 和 val[n+1] 可以认为是两个「虚拟气球」(其值为 1 )。那么问题就变成了：在一排气球中，请你戳破气球 0 和气球 n+1 之间的所有气球（不包括 0 和 n+1），使得最终只剩下气球 0 和气球 n+1 两个气球，最多能够得到多少分？

那么现在就可以定义确定状态：dp[i][j] = x 表示，戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最高分数为 x。
状态转移方程为：

由于 (i, k) 和 (k, j) 是开区间，dp[i][k] 和 dp[k][j] 不会影响气球 k；而戳破气球 k 时，旁边相邻的就是气球 i 和气球 j 了，最后还会剩下气球 i 和气球 j，这也恰好满足了 dp 数组开区间的定义。这样就可以确保子问题的独立性了。

枚举 i，j，k ，确定所有状态，最后返回 dp[0][n + 1] 即可。


-下面代码(从下到上 从左到右遍历)

class Solution {
public:
    int maxCoins(vector<int>& nums) {
    	int n = nums.size();
		vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
		vector<int> val(n + 2);
		val[0] = val[n + 1] = 1;
		for(int i = 1; i <= n; i++) {
			val[i] = nums[i - 1];
		}
		
		for(int i = n - 1; i >= 0; i--) {
			for(int j = i + 2; j <= n + 1; j++) {
				for(int k = i + 1; k < j; k++) {
					int sum = val[i] * val[k] * val[j] + dp[i][k] + dp[k][j];
					dp[i][j] = max(dp[i][j], sum);
				}
			}
		}
		
		return dp[0][n + 1];
    }
};

-下面代码(从左到右 从下到上遍历)

class Solution {
public:
    int maxCoins(vector<int>& nums) {
    	int n = nums.size();
		vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
		vector<int> val(n + 2);
		val[0] = val[n + 1] = 1;
		for(int i = 1; i <= n; i++) {
			val[i] = nums[i - 1];
		}
		
		for(int j = 2; j <= n + 1; j++) {
			for(int i = j - 2; i >= 0; i--) {
				for(int k = j - 1; k > i; k--) {
					int sum = val[i] * val[k] * val[j] + dp[i][k] + dp[k][j];
					dp[i][j] = max(dp[i][j], sum);
				}
			}
		}
		
		return dp[0][n + 1];
    }
};