***Leetcode 312. Burst Balloons

本文主要是介绍***Leetcode 312. Burst Balloons，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/burst-balloons/description/

果然一碰到hard的dp就跪...

这里有个很好的思考问题过程 https://leetcode.com/problems/burst-balloons/discuss/76228/Share-some-analysis-and-explanations

首先是尝试想暴力，然后看到底是哪里重复计算了。

然后考虑分治，然后想到先找到最后一个删除的数字，这样的话 最后一次获得的就是1 * nums[i] * nums[n]。而且从i切分的两段是完全独立的子问题了。

这里还有个dp的图的解释：https://leetcode.com/problems/burst-balloons/discuss/76230/C++-dp-detailed-explanation

class Solution {
public:int maxCoins(vector<int>& A) {vector<int> nums;nums.push_back(1);for (int i = 0; i < A.size(); i++) nums.push_back(A[i]);nums.push_back(1);// vector<int> dp( nums.size(), 0 );int dp[nums.size()+1][nums.size()+1];memset(dp, 0, sizeof(dp));int n = nums.size();for (int len = 2; len <  n; len ++) {for (int left = 0; left < n - len; left ++) {int right = len + left;for (int i = left+1; i <  right; i++) {dp[left][right]  = max(dp[left][right], nums[i] * nums[left] * nums[right] + dp[left][i] + dp[i][right] );}}}return dp[0][nums.size()-1];}
};

这篇关于***Leetcode 312. Burst Balloons的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---