)
题解https://qoogle.top/leetcode-312-burst-balloons/. - 力扣LeetCodedp[i][j] 表示从(i,j)区间戳破气球获得最大数量这个区间不包含戳破i和j这样从(i,k) 和(k,j)这样把这两个区间先戳破后最后剩下nums[k]这个位置戳破dp[i][k] dp[k][j] nums[i] * nums[k] * nums[j];class Solution { public: int maxCoins(vectorint nums) { int n nums.size(); if (n 0) { return 0; } nums.insert(nums.begin(), 1); nums.push_back(1); vectorvectorint memo(nums.size(), vectorint(nums.size(), -1)); return dfs(nums, 0, nums.size()-1, memo); } int dfs(const vectorint nums, int left, int right, vectorvectorint memo) { if (left 1 right) { return 0; } if (memo[left][right] ! -1) { return memo[left][right]; } int result 0; for (int i left1; i right; i) { int l dfs(nums, left, i, memo); int r dfs(nums, i, right, memo); result max(result, l r nums[left] * nums[i] * nums[right]); } memo[left][right] result; return result; } };class Solution { public: int maxCoins(vectorint nums) { if (nums.size() 0) { return 0; } nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); vectorvectorint dp(nums.size(), vectorint(nums.size(), 0)); for (int len 3; len nums.size(); len) { for (int i 0; ilen-1 nums.size(); i) { int left i; int right ilen-1; for (int k left1; k right; k) { int val nums[left] * nums[k] * nums[right]; dp[left][right] max(dp[left][right], dp[left][k] val dp[k][right]); } } } return dp[0][nums.size()-1]; } };正向思考以 [3, 1, 5][3,1,5] 为例对于第一次选择我们有三种选择。选择 3 将问题分解为左边的子问题 [][] 和 右边子问题 [1, 5][1,5]其解等于 [] [1, 5] 1 * 3 * 1[][1,5]1∗3∗1选择1 将问题分解为左边的子问题 [3][3] 和 右边子问题 [5][5]其解等于 [3] [5] 3 * 1 * 5[3][5]3∗1∗5选择5 将问题分解为左边的子问题 [3, 1][3,1] 和 右边子问题 [][]其解等于 [3, 1] [] * 1 * 5 * 1[3,1][]∗1∗5∗1发现上面的解时错的。因为正向思考的情况下以选择 1 为例在点爆 1 气球后两个左右子问题并不是独立的所以这给计算子问题带来了障碍怎么处理才能忽略中间的 1 呢逆向思考以 [3, 1, 5][3,1,5] 为例首先拿一个气球把这个气球当做最后一个气球然后点爆它。这样就能够将这个气球的左右两个子问题独立开。换种方式来说我们选这1这个气球然后优先点爆左边和右边的气球之后再最后点爆这个气嘴这时可以看出左右两个子问题是独立的他们只和1这个气球有关联。定义状态转移方程dp[i][j] 从 i到 j个气球闭区间能够获取的最大的硬币数量dp[i][j] dp[i][k - 1] dp[k 1][j] nums[i - 1] * nums[k] * nums[j 1] (i k j)这种方式仍然是O(n!)但是由于利用了“记忆化”的特性将重复的子问题写在了内存中保证每一种子问题只计算一遍。这时能够通过但是还可以优化。class Solution { private: vectorvectorint dp; int helper(vectorint nums, int i, int j) { // boundary if (i j) return 0; if (dp[i][j] 0) return dp[i][j]; // search for (int k i; k j; k) { int left helper(nums, i, k - 1); int right helper(nums, k 1, j); int delta nums[k] * nums[i - 1] * nums[j 1]; dp[i][j] max(dp[i][j], left right delta); } return dp[i][j]; } public: int maxCoins(vectorint nums) { int n nums.size(); nums.insert(nums.begin(), 1); nums.push_back(1); dp vectorvectorint(n 2, vectorint(n 2, 0)); int ans helper(nums, 1, n); return ans; } };class Solution { public: /** * param nums: A list of integer * return: An integer, maximum coins */ int maxCoins(vectorint nums) { // write your code here if (nums.size() 0) { return 0; } int size nums.size()2; nums.insert(nums.begin(), 1); nums.push_back(1); // i,j之间的吹爆的和是多少不包含ij位置 std::vectorstd::vectorint dp(size, std::vectorint(size, 0)); for (int len 3; len nums.size(); len) { for (int i 0; i len - 1 nums.size(); i) { int j i len - 1; for (int k i1; k j; k) { dp[i][j] max(dp[i][j], dp[i][k] dp[k][j] nums[i] * nums[k] * nums[j]); } } } return dp[0][size-1]; } }; 
长河君 · 2026/10/13 6:46:22 · 阅读 1.2k 312.戳气球(区间dp)
题解https://qoogle.top/leetcode-312-burst-balloons/. - 力扣LeetCodedp[i][j] 表示从(i,j)区间戳破气球获得最大数量这个区间不包含戳破i和j这样从(i,k) 和(k,j)这样把这两个区间先戳破后最后剩下nums[k]这个位置戳破dp[i][k] dp[k][j] nums[i] * nums[k] * nums[j];class Solution { public: int maxCoins(vectorint nums) { int n nums.size(); if (n 0) { return 0; } nums.insert(nums.begin(), 1); nums.push_back(1); vectorvectorint memo(nums.size(), vectorint(nums.size(), -1)); return dfs(nums, 0, nums.size()-1, memo); } int dfs(const vectorint nums, int left, int right, vectorvectorint memo) { if (left 1 right) { return 0; } if (memo[left][right] ! -1) { return memo[left][right]; } int result 0; for (int i left1; i right; i) { int l dfs(nums, left, i, memo); int r dfs(nums, i, right, memo); result max(result, l r nums[left] * nums[i] * nums[right]); } memo[left][right] result; return result; } };class Solution { public: int maxCoins(vectorint nums) { if (nums.size() 0) { return 0; } nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); vectorvectorint dp(nums.size(), vectorint(nums.size(), 0)); for (int len 3; len nums.size(); len) { for (int i 0; ilen-1 nums.size(); i) { int left i; int right ilen-1; for (int k left1; k right; k) { int val nums[left] * nums[k] * nums[right]; dp[left][right] max(dp[left][right], dp[left][k] val dp[k][right]); } } } return dp[0][nums.size()-1]; } };正向思考以 [3, 1, 5][3,1,5] 为例对于第一次选择我们有三种选择。选择 3 将问题分解为左边的子问题 [][] 和 右边子问题 [1, 5][1,5]其解等于 [] [1, 5] 1 * 3 * 1[][1,5]1∗3∗1选择1 将问题分解为左边的子问题 [3][3] 和 右边子问题 [5][5]其解等于 [3] [5] 3 * 1 * 5[3][5]3∗1∗5选择5 将问题分解为左边的子问题 [3, 1][3,1] 和 右边子问题 [][]其解等于 [3, 1] [] * 1 * 5 * 1[3,1][]∗1∗5∗1发现上面的解时错的。因为正向思考的情况下以选择 1 为例在点爆 1 气球后两个左右子问题并不是独立的所以这给计算子问题带来了障碍怎么处理才能忽略中间的 1 呢逆向思考以 [3, 1, 5][3,1,5] 为例首先拿一个气球把这个气球当做最后一个气球然后点爆它。这样就能够将这个气球的左右两个子问题独立开。换种方式来说我们选这1这个气球然后优先点爆左边和右边的气球之后再最后点爆这个气嘴这时可以看出左右两个子问题是独立的他们只和1这个气球有关联。定义状态转移方程dp[i][j] 从 i到 j个气球闭区间能够获取的最大的硬币数量dp[i][j] dp[i][k - 1] dp[k 1][j] nums[i - 1] * nums[k] * nums[j 1] (i k j)这种方式仍然是O(n!)但是由于利用了“记忆化”的特性将重复的子问题写在了内存中保证每一种子问题只计算一遍。这时能够通过但是还可以优化。class Solution { private: vectorvectorint dp; int helper(vectorint nums, int i, int j) { // boundary if (i j) return 0; if (dp[i][j] 0) return dp[i][j]; // search for (int k i; k j; k) { int left helper(nums, i, k - 1); int right helper(nums, k 1, j); int delta nums[k] * nums[i - 1] * nums[j 1]; dp[i][j] max(dp[i][j], left right delta); } return dp[i][j]; } public: int maxCoins(vectorint nums) { int n nums.size(); nums.insert(nums.begin(), 1); nums.push_back(1); dp vectorvectorint(n 2, vectorint(n 2, 0)); int ans helper(nums, 1, n); return ans; } };class Solution { public: /** * param nums: A list of integer * return: An integer, maximum coins */ int maxCoins(vectorint nums) { // write your code here if (nums.size() 0) { return 0; } int size nums.size()2; nums.insert(nums.begin(), 1); nums.push_back(1); // i,j之间的吹爆的和是多少不包含ij位置 std::vectorstd::vectorint dp(size, std::vectorint(size, 0)); for (int len 3; len nums.size(); len) { for (int i 0; i len - 1 nums.size(); i) { int j i len - 1; for (int k i1; k j; k) { dp[i][j] max(dp[i][j], dp[i][k] dp[k][j] nums[i] * nums[k] * nums[j]); } } } return dp[0][size-1]; } };