46. Translate numbers into strings

The title

Idea: Dynamic planning

• Dp [I] represents the number of types of strings translated from numbers ending in arr[I]
• If the current bit and the previous one form a 10-25 number, the current bit can be translated in two ways, either alone or together. So there are two sources of DP
• Analog jump step
• Transfer equation:dp[i] = dp[i - 1] + dp[i - 2]ordp[i] = dp[i - 1];

code

class Solution {
    public int translateNum(int num) {
        String str = String.valueOf(num);
        char[] arr = str.toCharArray();
        int length = arr.length;
        if (length == 1) return 1;/ / sentence
        int[] dp = new int[length];
        dp[0] = 1;
        String s = str.substring(0.2);
        int tmp = Integer.parseInt(s);
        if (tmp >= 10 && tmp <= 25) {// Two sources
            dp[1] = 2;
        } else {
            dp[1] = 1;
        }
        for (int i = 2; i < length; i++) {
            s = str.substring(i - 1, i + 1);// A string consisting of the current and previous bits
            tmp = Integer.parseInt(s);
            if (tmp >= 10 && tmp <= 25) {// Two sources
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1]; }}return dp[length - 1]; }}Copy the code