难度中等515
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"提示：
0 <= num < 231
动态规划
状态方程的推导：
上面是参考的推导过程，那么其实这道题是和青蛙跳台阶是一个道理的，只不过青蛙跳台阶可以选择跳一步或者两步，但是我们这道题对整数的翻译，只能确定翻译一个，但是翻译两个的话是有条件的，也就是要两个的和 10 <= tmp <= 25 才要判断加入翻译两个的情况！
所以方法就是总结如下：
- 先给定一个
pre和pre_pre分别代表前一个和再前一个它们代表的 dp 值 - 从倒数第二位开始不断取
num的低位（高位也行，取低位比较方便），然后不断与它旁边一位求和并进行判断 - 若满足翻译两个的条件也就是
10 <= tmp <= 25，则让dp[i] = pre + pre_pre，否则的话就只有dp[i] = pre - 循环上述过程直到
num为0
class Solution {
public:
int translateNum(int num) {
int pre = 1;
int pre_pre = 1;
int x, y = num % 10;
// 从低位到高位判断
while(num)
{
num /= 10;
x = num % 10;
int tmp = x*10 + y;
// 判断两位是否能被翻译，并对应其状态方程
if(tmp > 25 || tmp < 10)
tmp = pre;
else
tmp = pre + pre_pre;
// 不断更新状态
pre_pre = pre;
pre = tmp;
y = x; // 记得也要更新y
}
return a;
}
};