给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

看到该题的第一个想法就是使用动态规划求解，而动态规划的核心就是写出解题的方程
对于这个题目来说，因为数字只能一位一位的翻译或者两位一起翻译
当我们将长度为n的数字最后一位单独翻译的时候，其解法与n-1的解法是相等的，即f(n)=f(n-1)
对于最后两位一起翻译，将后两位视作一个整体的话，其解法与n-2相同，但是由于后两位并不一定只能一起，所以还需要加上最后一位单独翻译的结果，即f(n)=f(n-1)+f(n-2)
而后两位一起翻译时是需要考虑这两位对应的数字是否在0-25之间，
当倒数第二位为0的时候，01-09显然不在，所以不能同时解析后两位，当两位表示的数字大于25时，也超出了翻译的最大范围，同样不满足条件，这时就只能将最后一位单独翻译
当最后两位在10-25之间时，这时候则可以将后两位一起翻译或者单独翻译最后一位
最后得到的结果就是

if 10<=最后两位<=25 
    f(n)=f(n-1)+f(n-2)
else
    f(n)=f(n-1)

实现

public int translateNum(int num) {
    String value = String.valueOf(num);
    if (value.length() == 1) {
        return 1;
    }
    int total = 1, a0, a1 = 1;
    for (int i = 1; i < value.length(); i++) {
        a0 = a1;
        a1 = total;
        char c1 = value.charAt(i - 1);
        char c2 = value.charAt(i);
        if (c1 == '1' || (c1 == '2' && c2 <= '5')) {
            total += a0;
        }
    }
    return total;
}

如果数字只有一位，那就只有一个解
total表示当前总的解，因为我们是从长度2开始遍历，所以total的取值跟长度1时相同
a0和a1表示f(0)和f(1)的解，也就是DP的边界值
每次循环的时候，n增加1，对应的a1变为f(n-2)的值，所以赋值给a0，total表示的到上次为止的所有解，即f(n-1)的值，所以赋值给a1
再判断n和n-1的组合值是不是在10到25之间，是的话，total就需要加上f(n-2)的值，即a0，否则就等于f(n-1)的值，就是其本身