题目描述：
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例1:
输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
解题思路：
1、动态规划： 定义f(i)表示从第i位数字结尾的不同翻译的数量，那么有两种情况：
（1）当第i位和第i - 1位的两位数字拼接起来的数字在10-25的范围内，有两种解释的方式，分别是1、第i位数字翻译为一个字母；2、第i位和第i - 1位的两位数字拼接起来翻译为一个字母，此时f(i) = f(i -1) + f(i - 2);
（2）当第i位和第i - 1位的两位数字拼接起来的数字不在10-25的范围内，那么只有一种解释的方式，即第i位数字翻译为一个字母，此时f(i) = f(i -1);
初始化条件：f(0) = f(1) = 1，这是因为当num的第1, 2位的组成的数字在10-25的范围内时，显然应有2种翻译方法，即 f[2] = f[1] + f[0] = 2 ，而显然 f[1] =1 ，因此推出 f[0] = 1。
注： 动态规划的思想我采用了两种方式进行实现，一种是使用字符串进行遍历；另一种是直接对该数字进行取余操作。
2、递归： 递归的过程也是基于上述动态规划的转移方程进行的，这里就不再赘述了，具体实现可参见实现代码。
时间复杂度和空间复杂度： 动态规划的时间复杂度为O(log10num)，其中使用字符串进行遍历的实现方式的空间复杂度为O(log10num)，而直接对该数字进行取余操作的实现方式的空间复杂度为O(1)。
实现代码：
//解法1：动态规划 public int translateNum(int num) { String s = String.valueOf(num); int a = 1, b = 1;//a和b分别保存f(i)和f(i-1),初始化为a = f(1)，b = f(0) for(int i = 0; i <= s.length() - 2; i++){ String str = s.substring(i, i + 2); int c = str.compareTo("10") >= 0 && str.compareTo("25") <= 0 ? a + b : a; b = a; a = c; } return a; } //解法2：动态规划(优化空间复杂度） public int translateNum1(int num) { int a = 1, b = 1; int x, y = num % 10; while(num != 0){ num /= 10; x = num % 10; int temp = x * 10 + y; int c = temp >= 10 && temp <= 25 ? a + b : a; b = a; a = c; y = x; } return a; } //解法3：递归 public int translateNum2(int num) { if(num <= 9) return 1; int temp = num % 100; if(temp < 10 || temp > 25) return translateNum(num / 10); else return translateNum(num / 10) + translateNum(num / 100); }