题目详情
有 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
思路:
本题如果我们思考先戳破哪个气球,然后再分析两边情况,那么我们无法处理两边气球的
依赖关系,例如l mid r,我们戳破mid,那么再戳l又要考虑r,戳r要考虑l,无法分而治之
所以我们不妨反向思考,我们遍历假设某个气球不被戳破(即保留哪个气球),那么这时两边的
依赖关系就不存在了,就可以采用分治法处理了!
注意处理边界,两边加上1
class Solution
{
public:
vector> mp; //记忆化
vector rec; //记录气球值
int maxCoins(vector& nums)
{
int n = nums.size();
//rec记录气球值并在两边加上边界1
rec.push_back(1);
for (int i = 0; i < n; ++i)
rec.push_back(nums[i]);
rec.push_back(1);
//因为rec一共n+2个 所以mp要构造成 (n+2)*(n+2)的二维数组并初始化为-1
mp.resize(n + 2, vector(n + 2, -1));
return solve(0, n + 1);
}
int solve(int l, int r)
{
if (l + 1 >= r) return 0; //
if (mp[l][r] != -1) return mp[l][r]; //若(l,r)solve过则直接返回(记忆化)
//从第二个值开始(假设不被戳破)分治,直到遍历到r-1
for (int mid = l + 1; mid < r; ++mid)
{
int sum = rec[mid] * rec[l] * rec[r]; //每次初始化sum
//sum再加上两边的区间solve值
sum += solve(l, mid) + solve(mid, r);
//将mp[l][r]每次更新为较大值
mp[l][r] = max(sum, mp[l][r]);
}
return mp[l][r];
}
};
相似的道理,我们也可以使用从下到上的动态规划来解决:
class Solution
{
public:
int maxCoins(vector& nums)
{
int n = nums.size();
vector rec(n + 2);
vector> dp(n + 2, vector(n + 2, 0));
for (int i = 1; i <= n; i++) rec[i] = nums[i - 1];
rec[0] = rec[n + 1] = 1; //边界
for (int l = n; l >= 0; l--)
{ //逆序运算 前面会先使用后面保存的结果 从下而上
for (int r = l + 1; r <= n + 1; r++)
{
for (int mid = l + 1; mid < r; mid++)
{
dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid][r] + rec[mid] * rec[l] * rec[r]);
}
}
}
return dp[0][n + 1];
}
};
涉及知识点:
1.分治法
顾名思义，分治问题由“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子问题，再将子问题进行处理合并，从而实现对原问题的求解。例如归并排序就是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为 1 的子数组;“治”即为把已经排好序的两个小数组合成为一个排好序的大数组，从长度为 1 的子数组开始，最终合成一个大数组。
