## [面試題46. 把數字翻譯成字符串](https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/) > Medium #### 思路 首先分析一下題目，對于例子`12258` * 第一個字母可以選`1` 或 `12`，`122` 選不了了，因為`122` 超過了`$ [0, 25] $` 范圍。 * 如果第一個字母選了`1`，第二個可選`2`或`22`來翻譯；如果第一個拿個`12`來翻譯，第二個可以選`2`或`25`來翻譯。 * 明顯的，我們選擇形成了一個樹狀的結構，如下圖  * 樹的最后的子節點的個數，即我們最終的可翻譯的方法。 * 可看到分支很多都是相同的，比如圖中`2258`的子分支也出現在`258`的子分支當中，使用記憶化遞歸 * 中間有個小陷阱，有`0`的情況需要考慮進去 嘗試使用遞歸求解，AC！ #### 代碼 python3 ``` class Solution: @lru_cache(None) def dfs(self, res): if res == '': return 1 if int(res) < 10: return 1 result = 0 if int(res[0:2]) < 26 and int(res[0:2]) > 9: result += self.dfs(res[2:]) result += self.dfs(res[1:]) return result def translateNum(self, num: int) -> int: return self.dfs(str(num)) ``` 細心的小伙伴發現我們這道題放在了dp類別中，我們這題也可以使用動態規劃來做。（很多的dp題，我們都可以先考慮記憶化遞歸的方法，然后再轉化成bottom-up 動態規劃方法，這樣個人感覺思路會比較清晰） #### 轉換思路 * 我們從上面的圖可以看到，我們可以從最后的`8`為最小的元素，從下向上計算 * 使用這種方式計算，所有上層的結果都可以從我們已有的結果中獲取 * 其實這就是bottom-up的思想 * 對于我們這題，從前到后翻譯和從后到前翻譯，對于結果沒有影響。上圖中的自底向上，是從最后一個數字來考慮。暫時先忘了他，我們還是按正常思維從前到后來思考dp方法 * 構建dp數組，`dp[i]`表示翻譯到第i個數字時，可能的翻譯數量 * 對于`dp[i]`來說，有兩種可能性：可能是從`dp[i-1]`然后再加上第`i`個數字翻譯過來，也有可能從`dp[i-2]`然后再加上第`i-1`和`i`個數字，組成的翻譯 * 第`i-1`和第`i`個數子組成的數字，在`[10,25]`返回內才滿足上述的第二種可能性 * 通過上述思考我們可以得到**狀態轉移方程** ： ```[tex] dp[i] = \begin{cases} dp[i-1] + dp[i-2] &\text{if } num \in[10,25] \\ dp[i-1] &\text{if } num \notin [10,25] \end{cases} ``` * `dp[0] = 1`, 為了符合通項，我們設置0的情況的值為1 嘗試編寫一下代碼，AC！ #### 代碼 python3 ``` class Solution: def translateNum(self, num: int) -> int: dp = [0] * (len(str(num)) + 1) dp[0] = 1 dp[1] = 1 for i in range(2, len(str(num)) + 1): temp = int(str(num)[i-2:i]) if temp > 9 and temp < 26: dp[i] += dp[i-2] dp[i] += dp[i-1] print(dp) return dp[-1] ```