Leetcode: 312. Burst Balloons
Problem Statement
- Can we solve the problem from end to start? Instead of bursting from the first to the last balloon, we can burst from the last to the first since it is easier to know the last balloon's neighbors. Time and space complexity is \(O(n^2)\).
from typing import List
from functools import cache
class Solution:
def maxCoins(self, nums: List[int]) -> int:
N = len(nums)
@cache
def dfs(i, j):
if i > j:
return 0
ans = float("-inf")
for k in range(i, j + 1):
ans = max(
ans,
dfs(i, k - 1)
+ dfs(k + 1, j)
+ (nums[i - 1] if i - 1 >= 0 else 1)
* nums[k]
* (nums[j + 1] if j + 1 < N else 1),
)
return ans
return dfs(0, N - 1)
assert Solution().maxCoins([3, 1, 5, 8]) == 167
assert Solution().maxCoins([1, 5]) == 10
from typing import List
class Solution:
def maxCoins(self, nums: List[int]) -> int:
N = len(nums)
dp = [[0] * N for _ in range(N)]
for i in range(N - 1, -1, -1):
for j in range(i, N):
for k in range(i, j + 1):
dp[i][j] = max(
dp[i][j],
(dp[i][k - 1] if i <= k - 1 else 0)
+ (dp[k + 1][j] if k + 1 <= j else 0)
+ nums[k]
* (nums[i - 1] if i - 1 >= 0 else 1)
* (nums[j + 1] if j + 1 < N else 1),
)
return dp[0][N - 1]
assert Solution().maxCoins([3, 1, 5, 8]) == 167
assert Solution().maxCoins([1, 5]) == 10