爬樓梯模型

爬樓梯模型是動態規劃當中的一個經典模型，可以抽象為：在當前這一步，你有若干個可選的操作，比如前進一步或前進兩步，試問最少需要多少步能夠到達終點。一個可能的變形是每一步具有固定的代價，試問到達終點的最小代價是多少。

最經典的爬樓梯問題就是初始時你處于第一層（第零級臺階），每次可以爬一個臺階或兩個臺階，請問到達第 n 級臺階最少需要多少步。

依據這個最基本的爬樓梯模型，派生出了許多變體，參考靈茶山艾府整理的文檔：分享丨【算法題單】動態規劃（入門/背包/劃分/狀態機/區間/狀壓/數位/樹形/優化），將這些題目的思路在此進行收錄。

LeetCode 746. 使用最小花費爬樓梯

思路

可以看作是爬樓梯問題最簡單的變體，在爬樓梯的過程中為每一步引入了代價，試問爬到終點最小的代價是多少。

使用 dp 數組記錄的狀態就是爬到當前這一級臺階的最小代價，由此可以推出狀態轉移方程：dp[i] = min(dp[i - 1] + cost[i - 1] + dp[i - 2] + cost[i - 2])，根據狀態轉移方程直接寫代碼即可。

Golang 代碼

func minCostClimbingStairs(cost []int) int {n := len(cost)if n < 3 {return min(cost[0], cost[1])}dp := make([]int, n + 1)for i := 2; i <= n; i ++ {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])}return dp[n]
}

LeetCode 377. 組合總和 Ⅳ

思路

可以將最終的 target 視為要攀爬的目標樓梯數，將 nums 數組當中的數字視為一次行動可以攀爬的樓梯數，這道題目可以抽象為一個爬樓梯問題。

具體來說，使用 dp 數組記錄爬到某一層需要多少次行動，初始化 dp[0] = 1，作為動態規劃的邊界狀態。狀態轉移方程可以寫為：$dp[i]={\sum }_{j=0}^{n?1}dp[i?nums[j]$，前提是$i\ge nums[j]$。

Golang 代碼

func combinationSum4(nums []int, target int) int {n := len(nums)dp := make([]int, target + 1)dp[0] = 1for i := 1; i <= target; i ++ {for j := 0; j < n; j ++ {if i >= nums[j] {dp[i] += dp[i - nums[j]]}}}return dp[target]
}

LeetCode 2466. 統計構造好字符串的方案數

思路

從這一題開始，稍有難度。其實這道題本質上也是一個爬樓梯問題，zero 和 one 指的就是一次行動可以攀爬的樓梯數，只要爬上的臺階大于等于 low，就可以記錄答案。

使用 dp 數組記錄的是構造長度為 i 的字符串的方案數，只要 i 大于等于 low，那么dp[i]就是答案的一部分。

可以得到初步的狀態轉移方程：

dp[i]=dp[i-one]+dp[i-zero]

還需要考慮由于答案可能過大的取模情況，詳見代碼。

Golang 代碼

func countGoodStrings(low int, high int, zero int, one int) int {dp := make([]int, high + 1)dp[0] = 1const MOD int = 1e9 + 7ans := 0for i := 1; i <= high; i ++ {if i >= zero {dp[i] = dp[i - zero] % MOD}if i >= one {dp[i] = (dp[i] + dp[i - one]) % MOD}if i >= low {ans = (ans + dp[i]) % MOD}}return ans
}

LeetCode 2266. 統計打字方案數

思路

這應該是靈神題單里最難的一道題，實際上也是一道爬樓梯問題。具體來說，根據不同數字的重復數，每一個號碼能夠構造出的字母方案可以被視為一個爬樓梯問題。比如對于數字 3，它對應的字符是“def”，如果按 1 次 3，那么只能構造出 d，如果按 2 次，可以構造出 dd 或 e，按 3 次，可以構造出 ddd/de/f/ed，使用 dp 來記錄重復號碼可能構造出的字符數，對于 7 和 9 之外的號碼，狀態轉移方程是dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]，而對于 7 和 9 這兩個有四個字符的號碼，狀態轉移方程是dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4]。預先將這兩個 dp 數組處理出來即可。

每一次對一段重復的號碼進行統計（最小的重復數是 1，也就是只按下一次這個按鍵），之后如果號碼不再重復，就統計答案，這里要用到乘法原理，因為不同號碼構造出的可能字符數的情況是互斥的。

Golang 代碼

func countTexts(pressedKeys string) int {const MOD int = 1e9 + 7n := len(pressedKeys)dp3 := []int{1, 1, 2, 4}dp4 := []int{1, 1, 2, 4}for i := 4; i <= n; i ++ {dp3 = append(dp3, (dp3[i - 1] + dp3[i - 2] + dp3[i - 3]) % MOD)dp4 = append(dp4, (dp4[i - 1] + dp4[i - 2] + dp4[i - 3] + dp4[i - 4]) % MOD)}ans, cnt := 1, 1    // ans 記錄最終的答案, cnt 記錄當前字符的重復數for i := 1; i < n; i ++ {if pressedKeys[i] == pressedKeys[i - 1] {// 當前字符和前一個字符重復, cnt ++cnt ++} else {// 當前字符和前一個字符不重復, 此時要做的就是統計答案// 需要注意的是, 現在統計的是前一個字符的答案, 當前字符要在下一次 pressedKeys[i] != pressedKeys[i - 1] 的時候統計// 這就意味著 i == n - 1 的情況需要在這個 for loop 之后單獨考慮if pressedKeys[i - 1] == '7' || pressedKeys[i - 1] == '9' {ans = ans * dp4[cnt] % MOD} else {ans = ans * dp3[cnt] % MOD}cnt = 1 // 重復的字符數重置為 1}}if pressedKeys[n - 1] == '7' || pressedKeys[n - 1] == '9' {ans = ans * dp4[cnt] % MOD} else {ans = ans * dp3[cnt] % MOD}return ans
}