原题
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例1:
输入： 12258
输出： 5
解释： 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示:
- 0 <= num < 231
解法
思想
动态规划：
可以使用leetcode70-爬楼梯的思想，每次翻译一位数看成跳一步，翻译两位数看成跳两步，那么对于任意要跳的一个位置来说，例如12258中的8，由于最后两位是58不能翻译，也就是只能由1225跳过来，此时f(12258)==f(1225)，而对于1225，由于最后两位是25可以翻译，所以可以从12跳过来，也可以从122跳过来，此时f(1225) == f(12)+f(122)。将这两种情况一般化就能得出结论：
代码
class Solution {
public int translateNum(int num) {
if(num == 0) return 1;
if(num < 10) return 1;
int left = num%10;
//去除最后一位数的last
int last = num/=10;
//计算出最后两位数的大小
left = 10*(num%10)+left;
//去除最后两位数的lastOfLast
int lastOfLast = num /= 10;
if(left>25||left<10) return translateNum(last);
else return translateNum(last)+translateNum(lastOfLast);
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%89%91%e6%8c%87offer46-%e6%8a%8a%e6%95%b0%e5%ad%97%e7%bf%bb%e8%af%91%e6%88%90%e5%ad%97%e7%ac%a6%e4%b8%b2/
