給定 n 個氣球，每個氣球上有一個數字。戳破氣球 i 可獲得
nums[i-1] * nums[i] * nums[i+1]的硬幣，戳破後左右氣球變為相鄰。求能收集的最大硬幣數。
Example:
Input: nums = [3,1,5,8] Output: 167
Intuition
TIP
逆向思考：不是決定先戳哪個，而是決定在區間 (i, j) 中「最後戳哪個」氣球 k。
- 正向思考（先戳哪個）很難處理，因為戳破後陣列結構改變
- 逆向思考：
dp[i][j]代表戳破 (i, j) 開區間內所有氣球能獲得的最大硬幣 - 選擇 k 作為最後一個戳破的氣球，此時 k 的左右鄰居就是 i 和 j
- 轉移：
dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) - 在 nums 前後各加一個 1，方便處理邊界
Approaches
1. Memoized Search (Top-Down) — O(n^3) / O(n^2)
- Idea: 遞迴 + memo，枚舉區間內最後被戳破的氣球。
- Time:
O(n^3) - Space:
O(n^2)
class Solution {
fun maxCoins(nums: IntArray): Int {
val n = nums.size
val extended = IntArray(n + 2)
extended[0] = 1
extended[n + 1] = 1
for (i in nums.indices) extended[i + 1] = nums[i]
val memo = Array(n + 2) { IntArray(n + 2) { -1 } }
return dp(extended, memo, 0, n + 1)
}
private fun dp(nums: IntArray, memo: Array<IntArray>, left: Int, right: Int): Int {
if (left + 1 == right) return 0
if (memo[left][right] != -1) return memo[left][right]
var result = 0
for (k in left + 1 until right) {
result = maxOf(
result,
dp(nums, memo, left, k) + dp(nums, memo, k, right) +
nums[left] * nums[k] * nums[right]
)
}
memo[left][right] = result
return result
}
}⭐ 2. Interval DP (Bottom-Up) — O(n^3) / O(n^2)
- Idea: 按區間長度從小到大填表，
dp[i][j]為開區間 (i, j) 的最大硬幣數。 - Time:
O(n^3) - Space:
O(n^2)
class Solution {
fun maxCoins(nums: IntArray): Int {
val n = nums.size
val extended = IntArray(n + 2)
extended[0] = 1
extended[n + 1] = 1
for (i in nums.indices) extended[i + 1] = nums[i]
val dp = Array(n + 2) { IntArray(n + 2) }
for (len in 2..n + 1) {
for (i in 0..n + 1 - len) {
val j = i + len
for (k in i + 1 until j) {
dp[i][j] = maxOf(
dp[i][j],
dp[i][k] + dp[k][j] + extended[i] * extended[k] * extended[j]
)
}
}
}
return dp[0][n + 1]
}
}🔑 Takeaways
- Pattern: 區間 DP — 枚舉區間內「最後操作」的元素
- Key trick: 當「先做什麼」很難分析時，試著逆向思考「最後做什麼」；在陣列兩端加哨兵值簡化邊界處理