312. Burst Balloons - cocoder39/coco39_LC GitHub Wiki
Notes 2020:
My first idea was dp[i][j] = max(dp[i][j], dp[i][k] + nums[k-1]*nums[k]*nums[k+1] + dp[k][j]), but that's incorrect.
Suppose we burst nums[k] and divide the array to 2 subarrays [i..k-1] and [k+1..j], then when bursting nums[k-1], I would get nums[k-2]num[k-1]nums[k]. However, k should have been burst.
So we change the direction to think backward: try to add balloon one by one or say pick the last balloon to burst. So we got nums[left]*nums[i]*nums[right] + dp(i, right) + dp[left][i]
The key point is to identify what is stable: the score of burst last balloons is determined, then last but one is determined and so on.
T = O(n^3)
bottom-up DP
class Solution:
def maxCoins(self, iNums):
iNums = [1] + iNums + [1]
n = len(iNums)
dp = [[0]*n for _ in range(n)]
for k in range(2, n):
for left in range(0, n - k):
right = left + k
for i in range(left + 1,right):
dp[left][right] = max(dp[left][right],
iNums[left] * iNums[i] * iNums[right] + dp[left][i] + dp[i][right])
return dp[0][n - 1]
Top-down recursion
class Solution:
def maxCoins(self, nums: List[int]) -> int:
dummyNums = [1] + nums + [1]
n = len(dummyNums)
memo = [[-1] * n for i in range(n)]
def helper(left, right):
if left + 1 == right:
return 0
if memo[left][right] >= 0:
return memo[left][right]
res = 0
for i in range(left+1, right):
res = max(res, helper(left, i) + dummyNums[left]*dummyNums[i]*dummyNums[right] + helper(i, right))
memo[left][right] = res
return res
return helper(0, len(dummyNums)-1)
==============================================================================================================
supposing last is the last balloon we burst, then we have dp[left][right] = max(dp[left][right], nums[left-1]*nums[last]*nums[right+1] + dp[left][last-1] + dp[last+1][right]). Attention that nums[left-1]*nums[last]*nums[right+1] is correct while nums[last-1]*nums[last]*nums[last+1] is wrong.
time is O(n^3)
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
vector<vector<int>> dp(nums.size(), vector<int>(nums.size()));
for (int len = 1; len <= n; len++) {
for (int left = 1; left <= n - len + 1; left++) {
int right = left + len - 1;
for (int last = left; last <= right; last++)
dp[left][right] = max(dp[left][right], nums[left-1]*nums[last]*nums[right+1] + dp[left][last-1] + dp[last+1][right]);
}
}
return dp[1][n];
}