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

示例1:

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

思路

假設(shè)??₁??₂....??_???2的翻譯方式為??(???2)種
假設(shè)??₁??₂....??_???2??_???1的翻譯方式為??(???1)種

可以得出??₁??₂....??_???2??_???1??_??的翻譯方式

1. ??_???1和??_??可以組合翻譯那就可以選擇組合和不組合兩種，組合就是??(???2)種，不組合就是??(???1)種，一共??(???2)+??(???1)種

2. ??_???1和??_??不可以組合翻譯所以只有??(???1)種

由上面可以得出狀態(tài)轉(zhuǎn)移方程：

image.png

dp[1]=1,至于dp[0]為什么等于1，舉例：131,當讀到3是和前面的1可以組合翻譯應(yīng)該是dp[2]= dp[2-1]+dp[2-2]，可以看出來dp[2]明顯是2;所以dp[0]=1.
注意：dp[1]才是以第一個字符結(jié)尾的翻譯方案數(shù)而不是dp[0]，dp[0]只是為了方程的一個值

代碼

class Solution {
    public int translateNum(int num) {
    String str = num+"";
    String tmp="";
    int len = str.length();
    int []dp = new int[len+1];
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<len+1;i++){
       tmp = str.substring(i-2,i);
       if(tmp.compareTo("10")>=0&&tmp.compareTo("25")<=0){
            dp[i]=dp[i-1]+dp[i-2]; 
       }else{
           dp[i]=dp[i-1];
       } 
       
    }
    return dp[len];
    }
}

參考：
把數(shù)字翻譯成字符串