168. 吹气球中文English有n个气球编号为0到n-1每个气球都有一个分数存在nums数组中。每次吹气球i可以得到的分数为nums[left] * nums[i] * nums[right]left和right分别表示i气球相邻的两个气球。当i气球被吹爆后其左右两气球即为相邻。要求吹爆所有气球得到最多的分数。样例样例 1:输入[4, 1, 5, 10] 输出270 解释 nums [4, 1, 5, 10] 吹爆 1, 得分 4 * 1 * 5 20 nums [4, 5, 10] 吹爆 5, 得分 4 * 5 * 10 200 nums [4, 10] 吹爆 4, 得分 1 * 4 * 10 40 nums [10] 吹爆 10, 得分 1 * 10 * 1 10 总得分 20 200 40 10 270样例 2:输入[3,1,5] 输出35 解释 nums [3, 1, 5] 吹爆 1, 得分 3 * 1 * 5 15 nums [3, 5] 吹爆 3, 得分 1 * 3 * 5 15 nums [5] 吹爆 5, 得分 1 * 5 * 1 5 总得分 15 15 5 35注意事项你可以假设nums[-1] nums[n] 1。-1和n位置上的气球不真实存在因此不能吹爆它们。0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100这个题告诉我们欠的技术宅早晚要还区间dp基础题 放在面试里面都算是难的了for循环里面是遍历某一个点这个点是最后打的气球所以dp[x][y]dp[x][i-1] dp[i1][y] left*right*nums[i]注意的是 flag要在for循环后面因为for结束了才是当前区间遍历完class Solution { public: /** * param nums: A list of integer * return: An integer, maximum coins */ int dfs (int x, int y, vectorint nums, vectorvectorint dp, vectorvectorbool flag) { if (flag[x][y]) { return dp[x][y]; } int res 0; for (int i x; i y; i ) { dfs(x, i-1,nums,dp,flag); dfs(i1, y,nums,dp,flag); int left nums[x-1], right nums[y1]; res max(res, dp[x][i-1] dp[i1][y] left*right*nums[i]); } dp[x][y] res; flag[x][y] true; return dp[x][y]; } int maxCoins(vectorint nums) { // write your code here int n nums.size(); if (n 1) { return 0; } nums.insert(nums.begin(), 1); nums.push_back(1); vectorvectorintdp(n2,vectorint(n2,1)); vectorvectorboolflag(n2,vectorbool(n2,false)); return dfs(1,n,nums,dp,flag); } };