[数据结构与算法]剑指 Offer 46. 把数字翻译成字符串（动态规划解法）

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

分析：
用 dp(i)dp(i) 表示前 ii 个数字的翻译方法数
首先明确状态（显而易见了），接下来明确选择
我们可以有两种选择方式：①就单独排 ②和前面一个组合（前提是组合数得是10-25的）
接下来我们就可以写状态转移方程了

• 如果和前面的数字组合
  • 如果当前数可以和前面一个数字组合的话,dp(i)=dp(i?2);
  • 当前数字不能和前面一个数字组合的话，dp(i)=dp(i-1);
• 自己单排的话，dp(i)=dp(i-1);

动态规划解法

class Solution {
    public int translateNum(int num) {
        //dp[i] 表示前i个数字的翻译方法数。
        Integer number=num;
        String str=number.toString();
        int n=str.length();

        int dp[]=new int [n+1];
        dp[1]=1;
        for(int i=2;i<=n;i++){
            if(str.charAt(i-2)=='1'||(str.charAt(i-2)=='2'&&str.charAt(i-1)<'6')){
                if(i==2){
                    dp[i]=2;
                }else{
                   dp[i]=dp[i-1]+dp[i-2]; 
                }
            }else{
                dp[i]=dp[i-1];
            }
        }
        return dp[n];


    }
}