把数字翻译成字符串

题目链接: https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

image.png

题目解析
这道题采用动态规划解决

动态规划流程.png 解析

public int translateNum(int num) {
    // fn = fn-1 || fn = fn-1 + fn-2

    String s = String.valueOf(num);

    int[] dp = new int[s.length()+1];
    dp[0] = 1;
    dp[1] = 1;

    for (int n = 2; n < s.length()+1 ; n++) {
        String temp = s.substring(n-2,n);
        if (temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0 ){
            dp[n] = dp[n-1] + dp[n-2];
        }else {
            dp[n] = dp[n-1];
        }
    }

    return  dp[s.length()];
}

复杂度分析
空间复杂度: O(N)。
时间复杂度: O(N)。

这里空间复杂度可以进行优化为O(1)：

public int translateNum(int num) {
    // fn = fn-1 || fn = fn-1 + fn-2

    String s = String.valueOf(num);

    int fn1 = 1;
    int fn2 = 1;

    for (int n = 2; n < s.length()+1 ; n++) {
        String temp = s.substring(n-2,n);
        int fn = temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0 ? fn2 + fn1 : fn1;
        fn2 = fn1;
        fn1 = fn;
    }
    return  fn1;
}