我是小張同學(xué)，立志用更簡潔的代碼做更高效的表達(dá)

---

給定一個(gè)數(shù)字，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” ，1 翻譯成 “b”，……，11 翻譯成 “l(fā)”，……，25 翻譯成 “z”。一個(gè)數(shù)字可能有多個(gè)翻譯。請編程實(shí)現(xiàn)一個(gè)函數(shù)，用來計(jì)算一個(gè)數(shù)字有多少種不同的翻譯方法。

示例 1:
?
輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯，分別是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

提示：
?
0 <= num < 231

這是一道典型的動態(tài)規(guī)劃題目。對于一個(gè)數(shù) num[i]，我們有兩種選擇：

只翻譯自己；
和前面的數(shù)字組合翻譯，前提是組合的數(shù)在 $10?25$ 之間。
我們可以用 $dp(i)$ 表示前 $i$ 個(gè)數(shù)字的翻譯方法數(shù)。根據(jù)以上兩種選擇，我們進(jìn)行如下分析：

*如果只翻譯自己，比如 $12345$，如果 $5$ 單獨(dú)翻譯，那么方法數(shù)與 $1234$ 是一樣的， $dp(i)=dp(i?1)$。
如果和前面的數(shù)字組合，比如 12351235，如果 3535 組合翻譯，從兩方面考慮：
$35$ 看成一個(gè)整體，雖然加了 55 但是和沒加是一樣的，狀態(tài) $dp(i)=dp(i?1)$；
$35$ 組合就意味著不能再組合了，相當(dāng)于條件 $1$ 中的單獨(dú)翻譯自己，方法數(shù)與 $12$ 是一樣的。這時(shí) $dp(i)=dp(i?2)$
以上兩種情況相加即可。
故狀態(tài)轉(zhuǎn)移函數(shù)為：

$$dp(i)=\{\begin{array}{ll}dp(i?2)+dp(i?1)& \text{前面兩個(gè)數(shù)在1–25之間}\\ dp(i?1)& \text{else}\end{array}$$

再考慮邊界條件：

$$dp(0)=dp(1)=1$$

注意：條件 $1$ 星號處不是 $dp(i)=dp(i?1)+1$。比如 $12$ 如果 $2$ 單獨(dú)翻譯，$12$ 只有一種翻譯方法。

C++動態(tài)規(guī)劃解法

class Solution { public:int translateNum(int num) {string str = to_string(num);int len = str.size();if(len < 2) return len;vector<int> dp(len+1);dp[1] = 1;dp[0] = 1;for(int i = 2;i <= len;i++){int n = (str[i-2] - '0') * 10 + (str[i-1] - '0');if(n >= 10 && n <= 25) dp[i] = dp[i-2]+dp[i-1];else dp[i] = dp[i-1];}return dp[len];} };

---

此外，還有一種更簡潔的數(shù)字求余+遞歸方法

class Solution { public:int translateNum(int num) {if(num > 9 && num < 26) return 2;else if(num < 100) return 1;if(num % 100 > 25 || num % 100 < 10) return translateNum(num/10);else return translateNum(num/10) + translateNum(num/100);} };

總結(jié)

以上是生活随笔為你收集整理的【千字分析】剑指 Offer 46. 把数字翻译成字符串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。