动态规划之数字与字符串对应问题

题目

规定1对应A，2对应B，3对应C...26和Z对应。

然后一个数字符串，如“111”，可以转化为：“AAA"、"KA"和"AK"。

给出一个由数字字符组成的字符串str，有多少转换结果可以返回？

转换时，要么取一个字符，要么取两个字符。注：“0”的情况毫无意义。如果两个字符不超过26，只有26个字母，最大字母为Z

///暴力递归法public static int convertToStringOne(String str){    ///边界判断    if(str == null || str.length() == 0){        return 0;    }    ///字符串转换为数组    char[] chars = str.toCharArray();    int result = convertOne(chars, 0);    return result;}public static int convertOne(char[] chars, int index){    ////下标越界直接返回    if(index == chars.length){        return 1;    }    ///O开头无效解，直接返回    if(chars[index] == '0'){        return 0;    }    ////一个字符转动的情况    int ans1 = convertOne(chars, index + 1);    int ans2 = ans1;    //两个字符转动的情况，第一个字符不超过2，第二个字符不超过7，只有26个字符    if(index + 1 < chars.length &&  (chars[index] - '0')*10 + (chars[index + 1] - '0') < 27){        ans2 += convertOne(chars, index + 2);    }    return ans2;}

用数组存储已计算的结果。

///愚蠢的缓存法publicicc static int convertToStringTwo(String str){    ///边界判断    if(str == null || str.length() == 0){        return 0;    }    ///字符串转换为数组    char[] chars = str.toCharArray();    int N = chars.length;    ///缓存数组    int[] dp = new int[N];    int result = convertTwo(chars, 0, dp);    return result;}public static int convertTwo(char[] chars, int index, int[] dp){    ////下标越界直接返回    if(index == chars.length){        return 1;    }    if(dp[index] != 0){        return dp[index];    }    ///O开头无效解，直接返回    if(chars[index] == '0'){        return 0;    }    ////一个字符转动的情况    int ans1 = convertOne(chars, index + 1);    int ans2 = ans1;    第一个字符不超过2，第二个字符不超过7，只有26个字符    if(index + 1 < chars.length &&  (chars[index] - '0')*10 + (chars[index + 1] - '0') < 27){        ans2 += convertOne(chars, index + 2);    }    dp[index] = ans2;    return ans2;}

public static int convertToStringThree(String str){    ///边界判断    if(str == null || str.length() == 0){        return 0;    }    ///字符串转换为数组    char[] chars = str.toCharArray();    int N = chars.length;    ///缓存数组    int[] dp = new int[N+1];    ///最后一种情况 相当于 判断：    // if(index == chars.length){    //     return 1;    // }    dp[N] = 1;    //填结果    for (int i = N - 1; i >= 0; i--) {        //0 - N-1.判断“0”的情况        if(chars[i] != '0'){            int result = dp[i + 1];            if(i + 1 < chars.length && (chars[i] - '0')*10 + (chars[i + 1] - '0') < 27){                result += dp[i+2];            }            dp[i] = result;        }    }    return dp[0];}

public class ConvertToLetterString {    ///暴力递归法    public static int convertToStringOne(String str){        ///边界判断        if(str == null || str.length() == 0){            return 0;        }        ///字符串转换为数组        char[] chars = str.toCharArray();        int result = convertOne(chars, 0);        return result;    }    public static int convertOne(char[] chars, int index){        ////下标越界直接返回        if(index == chars.length){            return 1;        }        ///O开头无效解，直接返回        if(chars[index] == '0'){            return 0;        }        ////一个字符转动的情况        int ans1 = convertOne(chars, index + 1);        int ans2 = ans1;        第一个字符不超过2，第二个字符不超过7，只有26个字符        if(index + 1 < chars.length &&  (chars[index] - '0')*10 + (chars[index + 1] - '0') < 27){            ans2 += convertOne(chars, index + 2);        }        return ans2;    }    //傻缓存法    public static int convertToStringTwo(String str){        ///边界判断        if(str == null || str.length() == 0){            return 0;        }        ///字符串转换为数组        char[] chars = str.toCharArray();        int N = chars.length;        ///缓存数组        int[] dp = new int[N];        int result = convertTwo(chars, 0, dp);        return result;    }    public static int convertTwo(char[] chars, int index, int[] dp){        ////下标越界直接返回        if(index == chars.length){            return 1;        }        if(dp[index] != 0){            return dp[index];        }        ///O开头无效解，直接返回        if(chars[index] == '0'){            return 0;        }        ////一个字符转动的情况        int ans1 = convertOne(chars, index + 1);        int ans2 = ans1;        第一个字符不超过2，第二个字符不超过7，只有26个字符        if(index + 1 < chars.length &&  (chars[index] - '0')*10 + (chars[index + 1] - '0') < 27){            ans2 += convertOne(chars, index + 2);        }        dp[index] = ans2;        return ans2;    }    public static int convertToStringThree(String str){        ///边界判断        if(str == null || str.length() == 0){            return 0;        }        ///字符串转换为数组        char[] chars = str.toCharArray();        int N = chars.length;        ///缓存数组        int[] dp = new int[N+1];        ///最后一种情况 相当于 判断：        // if(index == chars.length){        //     return 1;        // }        dp[N] = 1;        //填结果        for (int i = N - 1; i >= 0; i--) {            //0 - N-1.判断“0”的情况            if(chars[i] != '0'){                int result = dp[i + 1];                if(i + 1 < chars.length && (chars[i] - '0')*10 + (chars[i + 1] - '0') < 27){                    result += dp[i+2];                }                dp[i] = result;            }        }        return dp[0];    }    public static String generateStr(int maxSize){        char[] chars = new char[maxSize];        for (int i = 0; i < maxSize; i++) {            int digital = (int)(10 * Math.random());            chars[i] = (char) (digital + '0');        }        return chars.toString();    }    public static void main(String[] args) {        System.out.println(测试开始:;        for (int i = 0; i < 10000; i++) {            ////随机生成字符串的大小            int maxSize = (int)(101 * Math.random());            String str = generateStr(maxSize);            int resultOne = convertToStringOne(str);            int resultTwo = convertToStringTwo(str);            int resultThree = convertToStringThree(str);            if(resultOne != resultTwo || resultOne != resultTwo || resultOne != resultThree || resultTwo != resultThree){                System.out.println(“不，小伙子，再看看！！");            }        }        System.out.println(“测试结束”;    }}