问题描述
有 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, 3, 1, 5, 8, 1]
(注意首尾的1
是后来单独插入的),这里我们考虑,假设最后一个戳爆的气球是5
,那么该问题就可以划分成戳[1, 3, 1, 5]
和戳[5, 8, 1]
两组气球的得分再加上最后戳爆气球5
的得分,(注意这里数组中的第一个和最后一个元素实际上都不是气球的元素,不能戳)。
从递归的角度来说,有dfs(nums, left, right) = max(dfs(nums, left, mid) + dfs(nums, mid, right) + nums[mid] * nums[l] * nums[r])
;但是这样直接递归必然导致超时,因此我们考虑采用一个数组cach[left][right]
来保存dfs(nums, left, right)
的结果,如果cach[left][right]
不为0,说明dfs(nums, left, right)
已经计算过了,不需要再重复计算了,直接return cach[left][right]
就好了。
动态规划
由上面的记忆化搜索,其实可以非常方便地改写成动态规划的形式,即
dp[left][right] = max(dp[left][right], dp[left][mid] + dp[mid][right] + nums[left] * nums[mid] * nums[right])
;
这里状态dp[left][right]
的定义为:开区间(left, right)
引爆气球所能获得的最大分数,mid
表示的是最后一个引爆的气球的坐标;
因此,这里要注意状态转移方程遍历的顺序。
代码
分治法+记忆化搜索
class Solution {
public:
保证子问题之间不存在依赖, 分治:递归搜索+保存计算结果
int dfs(vector<int> &nums, int left, int right, vector<vector<int>> &cach) {
if (left >= right) {
return 0;
}
int maxnum = 0;
for (int i = left + 1; i < right; i++) {
if (cach[left][right] > 0)
return cach[left][right];
else
maxnum = std::max(maxnum, nums[left] * nums[i] * nums[right] + dfs(nums, left, i, cach) + dfs(nums, i, right, cach));
}
cach[left][right] = maxnum;
return maxnum;
}
int maxCoins(vector<int> &nums) {
nums.insert(nums.begin(), 1);
nums.push_back(1);
int n = nums.size();
vector<vector<int>> cach(n, vector<int>(n, 0));
return dfs(nums, 0, n - 1, cach);
}
}
动态规划
#include <vector>
using std::vector;
class Solution {
public:
int maxCoins(vector<int> &nums) {
nums.insert(nums.begin(), 1);
nums.push_back(1);
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int l = n - 1; l >= 0; l--) { // 注意这里的遍历顺序!
for (int r = 0; r < n; r++) {
for (int mid = l + 1; mid < r; mid++) {
dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid][r] + nums[mid] * nums[l] * nums[r]);
}
}
}
return dp[0][n - 1];
}
};
错误示范
class Solution {
public:
int dfs(vector<int> &nums, set<int> &rset, set<int, std::greater<int>> &lset, vector<vector<vector<int>>> &cach, int n) {
if (rset.size() == 2)
return 0;
int maxnum = 0; //应该说递归,转化为子问题的时候就出问题了,完全变成回溯了
for (int i = 1; i <= n; i++) {
auto iter = rset.find(i);
if (iter != rset.end()) {
int idx_left = *lset.upper_bound(i);
int idx_right = *rset.upper_bound(i);
if (cach[i][idx_left][idx_right] > 0) {
maxnum = std::max(maxnum, cach[i][idx_left][idx_right]);
} else {
rset.erase(i);
lset.erase(i);
cach[i][idx_left][idx_right] = nums[i] * nums[idx_left] * nums[idx_right] + dfs(nums, rset, lset, cach, n);
maxnum = std::max(maxnum, cach[i][idx_left][idx_right]);
rset.insert(i);
lset.insert(i);
}
}
}
return maxnum;
}
int maxCoins(vector<int> &nums) {
set<int> rset;
set<int, std::greater<int>> lset;
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
for (int i = 0; i < nums.size(); i++) {
rset.insert(i);
lset.insert(i);
}
vector<vector<vector<int>>> cach(nums.size(), vector<vector<int>>(nums.size(), vector<int>(nums.size(), -1)));
return dfs(nums, rset, lset, cach, n);
}
};
这份代码,如果去掉保存计算结果的数组,就变成暴力回溯了,那么答案正确,但是会超时,加上保存计算结果的数组之后,答案则会出现错误,cach[i][left][right] = nums[i] * nums[idx_left] * nums[idx_right] + dfs(nums, rset, lset, cach, n);
从表面含义来看,是在当前气球排列为left, i, right
的情况下,戳爆i
所能获得的最大硬币数,问题在于,这样写的到的结果是[0,1,2], [1,2,3], [2,3,4]...[i - 1, i, rihgt]
中的最大值。