题目
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
解题
方法一：回溯
可以把这道题看成字符串分割，“0”~"25"之间的字符串才是符合题意的
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; } };
方法二：动态规划
根据动态转移方程的需要，将没有数字的时候，定义为可以翻译一种,即dp[0]=1;
因为dp[1]=1,可以根据dp[0]=1直接传递。
dp[2]可以根据dp[0]，dp[1]进行传递，值为1或者2
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]; } };
注意，必须要定义成vector dp(n+1,0)而不能是vector dp(n,0)
因为vector dp(n+1,0)初始化要定义dp[0]=1,dp[1]=1;
而vector dp(n,0)初始化不能定义成dp[0]=1,dp[1]=2,因为没法保证dp[1]=2,因为2个字符，可能是一种翻译，也可能是两种,这样子的话，就要在定义dp[1]的时候就要判断了，不能像上面一种定义那样，一起放在循环里判断。
