1. 題目

給定一個(gè)數(shù)字，我們按照如下規(guī)則把它翻譯為字符串：
0 翻譯成 “a” ，
1 翻譯成 “b”，……，
11 翻譯成 “l(fā)”，……，
25 翻譯成 “z”。

一個(gè)數(shù)字可能有多個(gè)翻譯。請(qǐng)編程實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)計(jì)算一個(gè)數(shù)字有多少種不同的翻譯方法。

示例 1: 輸入: 12258 輸出: 5 解釋: 12258有5種不同的翻譯， 分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"提示： 0 <= num < 2^31

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 動(dòng)態(tài)規(guī)劃，類(lèi)似斐波那契數(shù)列
• dp[i] 表示翻譯第 i 位字符時(shí)的方案數(shù)
• dp[0] 空串方案數(shù) 1
• dp[1] 第一位數(shù)只有1種翻譯
• str[i-2]=='1' ||(str[i-2]=='2' && str[i-1] <='5')，可以2個(gè)字符翻譯2個(gè)，也可以合并
• 其余情況，只能單獨(dú)翻譯成1個(gè)

class Solution { public:int translateNum(int num) {string str = to_string(num);int i, n = str.size();int dp[n+1] = {0};dp[0] = 1;//第0個(gè)字符空串dp[1] = 1;//第一個(gè)字符翻譯，只有1種可能for(i = 2; i <= n; ++i){if(str[i-2]=='1' ||(str[i-2]=='2' && str[i-1] <='5'))//該種情況，可以把這兩位數(shù)，翻成1個(gè)或者2個(gè)字符dp[i] = dp[i-2]+dp[i-1];else//34,29，只能單獨(dú)翻譯dp[i] = dp[i-1];}return dp[n];} };

總結(jié)

以上是生活随笔為你收集整理的剑指Offer - 面试题46. 把数字翻译成字符串（DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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