Description
有
n根高度各不相同的棍子排成一排，從左邊看過去恰好能看到k根。求排列方式的數量（結果對 10^9+7 取餘）。一根棍子「可見」代表它前面沒有更高的棍子。
Example:
Input: n = 3, k = 2 Output: 3
Intuition#
考慮最矮的棍子：如果它放在最前面就一定可見（+1 可見），否則它被前面的棍子擋住（不可見）。
dp[i][j]表示i根棍子中恰好看到j根的排列數- 最矮棍子放最前面：它一定可見，剩下
i-1根要看到j-1根 →dp[i-1][j-1] - 最矮棍子放在其他
i-1個位置之一：它一定被擋住，不影響可見數 →(i-1) * dp[i-1][j] - 轉移方程：
dp[i][j] = dp[i-1][j-1] + (i-1) * dp[i-1][j]
Approaches#
1: 2D DP#
- 概念: 建立
dp[n+1][k+1]表格，用上述轉移方程填表。 - 時間複雜度:
O(n * k) - 空間複雜度:
O(n * k)
class Solution {
fun rearrangeSticks(n: Int, k: Int): Int {
val MOD = 1_000_000_007L
val dp = Array(n + 1) { LongArray(k + 1) }
dp[0][0] = 1
for (i in 1..n) {
for (j in 1..minOf(i, k)) {
dp[i][j] = (dp[i - 1][j - 1] + (i - 1L) * dp[i - 1][j] % MOD) % MOD
}
}
return dp[n][k].toInt()
}
}⭐2: 1D DP（空間優化）#
- 概念: 由於
dp[i][j]只依賴dp[i-1][j-1]和dp[i-1][j]，可以壓縮為一維陣列，逆序更新。 - 時間複雜度:
O(n * k) - 空間複雜度:
O(k)
class Solution {
fun rearrangeSticks(n: Int, k: Int): Int {
val MOD = 1_000_000_007L
val dp = LongArray(k + 1)
dp[0] = 1
for (i in 1..n) {
for (j in minOf(i, k) downTo 1) {
dp[j] = (dp[j - 1] + (i - 1L) * dp[j] % MOD) % MOD
}
dp[0] = 0
}
return dp[k].toInt()
}
}🔑 Takeaways#
- Pattern: 組合 DP — 與 Stirling numbers of the first kind（第一類 Stirling 數）相關
- 關鍵技巧: 從最矮棍子出發思考（放最前面必可見，放其他位置必不可見），自然導出轉移方程