1. // 模型1：从左向右尝试模型
    3. /**
    4.  * 规定1-26与 a-k一一对应，那么给定一个数字字符组成的字符串str，返回有多少种转化结果
    5.  *    eg: ’111‘  可以转化为 AAA，KA，AK
    6.  */
    8. public class Code02_ConvertToLetterString {
    10.     // str只含有数字字符0~9
    11.     // 返回多少种转化方案
    12.     public static int number(String str) {
    13.         if (str == null || str.length() == 0) {
    14.             return 0;
    15.         }
    16.         return process(str.toCharArray(), 0);
    17.     }
    19.     // str[0..i-1]上已经转化无需过问
    20.     // str[i.....]去转化，返回有多少种转化方法，从index出发，后面所有的数字字符串转化完，有几种结果
    21.     public static int process(char[] str, int i) {
    22.         if (i == str.length) {
    23.             return 1;
    24.         }
    25.         // i没到最后，说明有字符
    26.         if (str[i] == '0') { // 之前的决定有问题
    27.             return 0;
    28.         }
    29.         // str[i] != '0'
    30.         // 可能性一，i位置字符独单转换，然后计算下一个位置（i+1位置）多少转换方案
    31.         int ways = process(str, i + 1);
    32.         // 可能性二，i位置和i+1位置的字符共同构成一个进行转换
    33.         if (i + 1 < str.length && (str[i] - '0') * 10 + (str[i + 1] - '0') < 27) {
    34.             ways += process(str, i + 2);
    35.         }
    36.         return ways;
    37.     }
    39.     public static int dp(String s) {
    40.         if (s == null || s.length() == 0) {
    41.             return 0;
    42.         }
    43.         char[] str = s.toCharArray();
    44.         int N = str.length;
    45.         int[] dp = new int[N + 1];
    46.         dp[N] = 1;
    47.         for (int i = N - 1; i >= 0; i--) {
    48.             if (str[i] != '0') {
    49.                 int ways = dp[i + 1];
    50.                 if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
    51.                     ways += dp[i + 2];
    52.                 }
    53.                 dp[i] = ways;
    54.             }
    55.         }
    56.         return dp[0];
    57.     }
    59.     public static void main(String[] args) {
    60. //        System.out.println(number("7210231231232031203123"));
    61. //        System.out.println(dp("7210231231232031203123"));
    62.         System.out.println('7'-'0');
    63.     }
    64. }