給定一個數(shù)字抵碟，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” 翩剪，1 翻譯成 “b”，……猖凛，11 翻譯成 “l(fā)”矫废，……盏缤，25 翻譯成 “z”。一個數(shù)字可能有多個翻譯蓖扑。請編程實現(xiàn)一個函數(shù)唉铜，用來計算一個數(shù)字有多少種不同的翻譯方法。
示例 1:
輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯律杠，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
思路：
一串數(shù)字字符串能組成多少個翻譯潭流，我們可以發(fā)下2個數(shù)字的翻譯是由1個數(shù)字再加最后一個數(shù)字組成的翻譯，3個數(shù)字的翻譯是由2個數(shù)字情況再加最后一個數(shù)字組成的翻譯柜去，4個數(shù)字的翻譯是由3個數(shù)字情況再加最后一個數(shù)字組成的翻譯灰嫉，一次類推，n個數(shù)字的翻譯是有n-1的情況與最后一個數(shù)字組成的翻譯嗓奢，這里就是一個典型的動態(tài)規(guī)劃的思路讼撒，如果我們要知道n個數(shù)字的翻譯數(shù)目是不是要知道n-1的翻譯數(shù)目然后在加上添加最后一個數(shù)字增加的種類即等于n個數(shù)字的翻譯數(shù)目。再此我們再分析最后一個數(shù)字放入考慮的情況是哪樣的，如果最后一個數(shù)字與前面一個數(shù)字組合不成一個新的字母椿肩，是不是即f(n) = f(n-1)(因為這個字母只能單獨存在瞻颂，只能把這個字母添加到原來種類的最后），如果最后一個數(shù)字能和前面的數(shù)字構成新的字母郑象，即f(n) = f(n-1) + f(n-2) 贡这，(因為要考慮兩種情況，如果不組成新的字母厂榛，總和等于f(n-1)盖矫，如果與前面那個數(shù)字組成新的字母，總和就等于f(n-2) ）击奶。
代碼：
#include<iostream>
using namespace std;
int translateNum(int num) {
if (num<=9)
{
return 1;
};
int current_num = num % 10+num/10%10*10;//得到最后兩個數(shù)字組合的大小
if (10<= current_num&& current_num<=25) //如果能組合成新的字母
{
return (translateNum(num / 100) + translateNum(num / 10 )); //總和等于f(n-2)+f(n-1)
}
else
{
return translateNum(num / 10);//否則等于f(n-1)
}
}
int main() {
cout << translateNum(12258) << endl;
}
