算法

(DP) $O(n)$

简单dp

Java 代码

class Solution {
    public int translateNum(int num) {
        // f(i)：以i为结尾的方法数
        // f(i) = + f(i - 1)
        // if a[i - 1] = 1: + f(i - 2)
        // if a[i - 2] = 2 & a[i] = [0, 5]: + f(i - 2)
        // f(0) = 1  f(-1) = 1
        int prev1 = 1; // 当前位翻译成单个字符的方法数
        int prev2 = 1; // 当前位与前一位合并翻译成单个字符的方法数
        String s = String.valueOf(num);
        int n = s.length();
        for (int i = 1; i < n; ++i) {
            int cur = prev1; // 当前的方法数
            char p = s.charAt(i - 1); // 前一位
            char c = s.charAt(i); // 当前位
            if (p == '1') cur += prev2;
            if (p == '2' && c >= '0' && c <= '5') cur += prev2;
            prev2 = prev1;
            prev1 = cur; 
        }
        return prev1;
    }
}