将字母A-Z编码，A为1，B为2，……依此类推，Z为26；则ABC编码为123。但是反向解码时，解码结果不唯一，比如123可以解码为 1-2-3：ABC，解码为12-3：LC，解码为1-23：AW（注意，127不能解码为1-27，因为范围只能为1-26）。
现给出一组编码后的数字串，让你求该数字串可以有几种解码方式（上例中，123对应着3种解码方式）。问题输入将保证其为一个合法的数字串。比如100是 一个不合法的数字串，因为0或者00不代表一个字母；此外01不能视为1。
Sample Input
25114 1111111111 3333333333
Sample Output
6 89 1
1 /* 2 * zoj 2022 来自大黄dp分类.. 一维dp..有点水,有点郁闷的地方就是0的处理... 3 * 递推公式: 4 * dp[i][j] = dp[i][j-2]; 当num[i] == 0; 5 * dp[i][j] = dp[i][j-1]+dp[i][j-2]; num[i] 和num[i-1]满足大于0小于27; 6 * dp[i][j] = dp[i][j-1]; 当num[i]和num[i-1]满足不了大于0小于27的情况时; 7 * zjy 2011 03 09 8 * */ 9 #include <stdio.h> 10 #include <string.h> 11 #define MAX 50000 12 int judge(char a,char b) 13 { 14 if(a=='0') 15 return 0; 16 if(a>'2') 17 return 0; 18 if(a=='2'&&b>'6') 19 return 0; 20 return 1; 21 } 22 int main(void) 23 { 24 char num[MAX]; 25 int dp[MAX]; 26 while (scanf("%s",num) != EOF && num[0]!='0') 27 { 28 int len = strlen(num); 29 memset(dp,0,sizeof(dp)); 30 dp[0]=1; 31 for (int i=1;i<len;i++) 32 { 33 if(num[i]=='0') 34 { if(i>=2) 35 dp[i] = dp[i-2]; 36 else 37 dp[i] = 1; 38 } 39 else if(judge(num[i-1],num[i])) //能够组成26以内的数; 40 { 41 if(i>=2) 42 dp[i]=dp[i-1]+dp[i-2]; 43 else 44 dp[i] = dp[i-1]+1; 45 } 46 else 47 dp[i] = dp[i-1]; 48 } 49 printf("%d\n",dp[len-1]); 50 } 51 return 0; 52 }
