剑指 Offer 46：把数字翻译成字符串

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

class Solution {
public:
    int res=0;
    bool isValid(string& strs,int start,int end){
        string s=strs.substr(start,end-start+1);
        if(s.size()==1&&s[0]<='9'&&s[0]>='0') return true;
        if(s.size()==2&&s>="10"&&s<="25") return true;
        return false;
    }
    void backtracing(string& strs,int startIndex){
        if(startIndex==strs.size()){
            res++;
            return;
        }
        for(int i=startIndex;i<strs.size();i++){
            if(isValid(strs,startIndex,i)){
                backtracing(strs,i+1);
            }
        }
    }
    int translateNum(int num) {
        string strs=to_string(num);
        backtracing(strs,0);
        return res;
    }
};

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