Description
給定
n個訂單，每個有取件 (Pi) 和送件 (Di)。取件必須在送件之前。求所有合法排列的數量，結果對10^9 + 7取模。
Example:
Input: n = 2 Output: 6
Intuition#
增量法：已排好 i-1 個訂單後，第 i 個訂單的 (Pi, Di) 有
(2i-1) * 2i / 2種插入方式。
- 已排好
i-1個訂單，序列長度為2(i-1) - 插入第
i個訂單的 Pi 和 Di，共有2i-1個空位放 Pi - Pi 放好後，Di 必須在 Pi 之後，有
(2i-1)到 1 個位置可選 - 每一步的方案數 =
(2i-1) * i=(2i-1) * 2i / 2
Approaches#
- Memoization (Top-Down DP) — O(n) / O(n)
- 概念: 直接照定義遞迴
f(i) = f(i-1) * (2i-1) * i，加 memo 快取 - 時間複雜度:
O(n)- 每個狀態只算一次 - 空間複雜度:
O(n)- memo 陣列 + 遞迴堆疊
class Solution {
fun countOrders(n: Int): Int {
val MOD = 1_000_000_007L
val memo = LongArray(n + 1) { -1L }
fun dp(i: Int): Long {
if (i == 1) return 1L
if (memo[i] != -1L) return memo[i]
memo[i] = dp(i - 1) * (2L * i - 1) % MOD * i % MOD
return memo[i]
}
return dp(n).toInt()
}
}- Bottom-Up DP — O(n) / O(n)
- 概念:
dp[i] = dp[i-1] * (2i-1) * i，逐步累乘 - 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun countOrders(n: Int): Int {
val MOD = 1_000_000_007L
val dp = LongArray(n + 1)
dp[1] = 1
for (i in 2..n) {
val slots = 2L * i - 1
dp[i] = dp[i - 1] * slots % MOD * i % MOD
}
return dp[n].toInt()
}
}⭐ 3. Math (Rolling Multiplication) — O(n) / O(1)
- 概念: 直接用變數累乘，不需陣列
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun countOrders(n: Int): Int {
val MOD = 1_000_000_007L
var result = 1L
for (i in 2..n) {
// 插入第 i 個訂單：Pi 有 (2i-1) 個空位
// Di 必須在 Pi 之後，平均有 i 個位置
// 方案數 = (2i-1) * i
result = result * (2L * i - 1) % MOD * i % MOD
}
return result.toInt()
}
}🔑 Takeaways#
- Pattern: 組合計數 DP — 增量插入法，每步計算新元素的插入方案數
- 關鍵技巧: 第 i 個訂單插入時，Pi 有
2i-1個間隔可放，Di 必須在 Pi 後面所以有(2i-1+1)/2 = i個有效位置（C(2i-1, 1) 選 Pi 位置，再從剩餘選 Di）