剑指 Offer 46. 把数字翻译成字符串

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int translateNum(int num) {
        String str = String.valueOf(num);

        // 定义 dp[i] 为第 i 个字符结尾的数字的方案数，此时 i 从 1 开始
        int[] dp = new int[str.length() + 1];
        dp[0] = 1;
        dp[1] = 1;

        // 此处注意 i 从 1 开始，故访问 str 时需要减去 1
        for (int i = 2; i <= str.length(); i++) {
            char x = str.charAt(i - 2), y = str.charAt(i - 1);
            if (x == '1' || (x == '2' && y <= '5')) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }

        return dp[str.length()];
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int translateNum(int num) {
        String numStr = String.valueOf(num);

        // 定义 dp[i] 表示截止至 numStr[i] 的翻译方法数
        int[] dp = new int[numStr.length()];
        dp[0] = 1;

        for (int i = 1; i < numStr.length(); i++) {
            // 作为一个字符进行翻译时
            dp[i] += dp[i - 1];

            // 作为两个字符进行翻译时，'10' -> '25'
            char p = numStr.charAt(i - 1), c = numStr.charAt(i);
            if (p == '1' || (p == '2' && (c >= '0' && c <= '5'))) {
                dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
            }
        }

        return dp[numStr.length() - 1];
    }
}

References

剑指 Offer 46. 把数字翻译成字符串