Brute force recursion to dynamic programming 04 (digital string conversion)

1. 题目

2. 暴力递归

Determine the termination conditions,If the selection ends at the last digit,Show that this choice is correct,返回1,如果遇到0,A single position cannot be changed to a letter;
Get the result of selecting the last bit first,Then determine whether there is a combination of the latter two,相加即可.

    public int number(String str) {
    
        return getNumber(str.toCharArray(), 0);
    }

    private int getNumber(char[] chars, int curIndex) {
    
        //If the last digit is reached,则返回 1
        if (curIndex == chars.length) {
    
            return 1;
        }

        //One can choose to change 或 change to two
        //Become one
        //如果当前值为 数字 0 ,There is no corresponding letter
        if (chars[curIndex] == '0') {
    
            return 0;
        }

        int ways = getNumber(chars, curIndex + 1);
        //change to two,一共26个字母
        if (curIndex + 1 < chars.length && (chars[curIndex] - '0') * 10 + (chars[curIndex + 1] - '0') < 27) {
    
            ways += getNumber(chars, curIndex + 2);
        }
        return ways;
    }

3. 动态规划

Dynamic programming can be evolved from brute force recursion,dpArrays are the only variables curIndex 的变化范围,为 [ 0 , chars.lengrth]
初始条件为 dp[ curIndex ] = 1,即终止条件
The rest is to change according to greed.

    public int number2(String str) {
    
        return getNumber2(str.toCharArray());
    }

    private int getNumber2(char[] chars) {
    
        int[] dp = new int[chars.length + 1];
        //Only the current position is a variable
        // 最后一位为1
        dp[chars.length] = 1;
        for (int curIndex = chars.length - 1; curIndex >= 0; curIndex--) {
    
            //This bit is not0
            if (chars[curIndex] != '0') {
    
                //This bit can be changed to a single letter
                int ways = dp[curIndex + 1];
                if (curIndex + 1 < chars.length && ((chars[curIndex] - '0') * 10 + (chars[curIndex + 1] - '0')) < 27) {
    
                    ways += dp[curIndex + 2];
                }
                dp[curIndex] = ways;
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
    
        System.out.println(new StrConvert().number("111"));
        System.out.println(new StrConvert().number2("111"));
    }