题目描述

题解

动态规划

一开始想通过寻找规律或者回溯法来遍历所有可能的情况, 但是都很复杂. 然后发现每增加一位数, 所得出的结果与之前的状态有着固定的转换关系, 所以果断使用动态规划来做!
*状态定义: *dp[i]表示使用所给整数的从左数1到i个数字有多少种不同的翻译.

*状态转移: * 很容易找出不同状态间的转移方程. 设已知dp[i-1]=3, 如何得到dp[i]? 首先, 无论输入整数的第i位是什么数字, 它所代表的字母都可以单独挂接在dp[i-1]的所有翻译结果后面, 如果输入整数的i-1位与第i位所组成的两位数小于26, 那么可以挂接在dp[i-2]的所有翻译结果后面, 所以状态转移方程为:

dp[i] = dp[i - 1];
if (arr.get(i - 2) != 0 && (arr.get(i - 2) * 10 + arr.get(i - 1) < 26)) {
    dp[i] += dp[i - 2];
}

*输出: * dp[nums的位数]

public int translateNum(int num) {
    if (num < 10) {
        return 1;
    }

    List<Integer> arr = new ArrayList<>();
    while (num != 0) {
        arr.add(num % 10);
        num /= 10;
    }
    Collections.reverse(arr);

    int[] dp = new int[arr.size() + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= arr.size(); i++) {

        dp[i] = dp[i - 1];
        if (arr.get(i - 2) != 0 && (arr.get(i - 2) * 10 + arr.get(i - 1) < 26)) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[arr.size()];

}