一、题目描述
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
0 <= num < 231
二、解题思路
对于我这种算法小白来说，碰到这种题，第一反应就是动态规划
只要能够按步骤画出表格来的，都可以用dp（动态规划来解），我们以12258为例
| 字符串 | 方案数 |
| 1 | 1 （b） |
| 12 | 2 （bc,j） |
| 122 | 3 （bcc,jc,bw） |
| 1225 | 5 （bccf,jcf,bwf,bcz,jz） |
| 12258 | 5 （bccfg,jcfg,bwfg,bczg,jzg） |
你发现规律了吗？
我们将每行的方案数保存到dp[]数组中，不难发现：首先，后面加上来的数本身作为一个数字时，拥有dp[i-1]中方案；而假如后面加上来的数能够和原本末尾的数发生组合，那么就多出了dp[i-2]种方案，所以，我们可以得到dp的递推式：
当后加的数能和末尾的数字组合（两个数字组合不超过25）时，dp[i] = dp[i-1] + dp[i-2]；
当后加的数不能和末尾的数字组合（两个数字组合超过25）时 ，dp[i] = dp[i-1]
三、java代码实现
1、动态规划
class Solution { public int translateNum(int num) { char []c = String.valueOf(num).toCharArray(); int len = c.length; int []dp = new int[len+1]; dp[0] = 1; dp[1] = 1; for(int i=2; i<len+1; i++) { if(c[i-2]=='0') { dp[i] = dp[i-1]; continue; } int temp = (c[i-2]-'0')*10+(c[i-1]-'0'); if(temp>=0 && temp<=25) { dp[i] = dp[i-1] + dp[i-2]; } else { dp[i] = dp[i-1]; } } return dp[len]; } }
时间复杂度： O(N)
空间复杂度： O(N)
2、滚动数组优化空间
可以看到，dp数组当前位的结果只与他前两个位置有关，所以我们可以用三个变量来保存，节省dp数组的空间。
时间复杂度： O(N)
空间复杂度： O(N)
3、优化保存num的数组
由动态规划的对称性可知，我们从后往前来判断，跟从前往后判断，得到的结果是一致的。因此我们可以利用取余直接拿到最后的几位数，省去用于存放num的空间。
class Solution { public int translateNum(int num) { int a = 1, b = 1, x, y = num % 10; while(num != 0) { num /= 10; x = num % 10; int tmp = 10 * x + y; int c = (tmp >= 10 && tmp <= 25) ? a + b : a; b = a; a = c; y = x; } return a; } }
时间复杂度： O(N)
空间复杂度： O(N)
