Description
Alice and Bob need to send secret messages to each other and are discussing ways to encode their messages: Alice: "Let's just use a very simple code: We'll assign `A' the code word 1, `B' will be 2, and so on down to `Z' being assigned 26." Bob: "That's a stupid code, Alice. Suppose I send you the word `BEAN' encoded as 25114. You could decode that in many different ways!" Alice: "Sure you could, but what words would you get? Other than `BEAN', you'd get `BEAAD', `YAAD', `YAN', `YKD' and `BEKD'. I think you would be able to figure out the correct decoding. And why would you send me the word `BEAN' anyway?" Bob: "OK, maybe that's a bad example, but I bet you that if you got a string of length 500 there would be tons of different decodings and with that many you would find at least two different ones that would make sense." Alice: "How many different decodings?" Bob: "Jillions!" For some reason, Alice is still unconvinced by Bob's argument, so she requires a program that will determine how many decodings there can be for a given string using her code.
Input
Input will consist of multiple input sets. Each set will consist of a single line of digits representing a valid encryption (for example, no line will begin with a 0). There will be no spaces between the digits. An input line of `0' will terminate the input and should not be processed
Output
For each input set, output the number of possible decodings for the input string. All answers will be within the range of a long variable.
Sample Input
25114111111111133333333330
Sample Output
6891 通过问题描述可以看出，该题目需要的是每次输入密文【一行数字】（输入的数字保证能解密出一串字母不出现无法解密的情况），输出该行密文可能解码出的答案数量。当输入密文为0时，退出程序。 单个数字组成的非0的个位数与两个相邻数字组成的在[1,26]区间的两位数都能找到对应的字母。 如题目中所提到25114可解析出6种答案， 2 5 1 1 4 25 1 1 4 2 5 11 4 25 11 4 2 5 1 14 25 1 14 可以用迭代的思想来考虑这个问题，设输入长度为n，当输入的最右位input[n-1]与其左边一位input[n-2]不能够组成1~26间的数字时，每个解密答案只是在后面加了一个字母，答案个数与输入为前n-1位的答案个数是一样的。如果能够组成1~26之间的数字，分为后两位结合与后两位分开两种情况，答案个数就等于输入前n-1位的答案个数加上输入前n-2位的答案个数。 即： f(n)=f(n-1) //组成>26 f(n)=f(n-1)+f(n-2) //组成<=26 当然，还要考虑到n=1的情况，此时不能访问f(n-2)，若组成<=26，则f(n)=2。 我的想法是用一个与输入长度一致的整数数组count[n]来存储答案个数，count[i]表示读取到输入的input[i]位时解密的答案个数。（应该是一种动态规划吧）
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 int main() { 8 string input; 9 //count存储当前位的答案数目，默认读取输入第一位时答案数目为110 int count[5000];11 count[0]=1;12 while(cin >> input && input != "0") {13 int n = input.size();14 for(int i = 1; i < n; i++) { //从输入第二位开始遍历15 //当前读取位为0的情况，此时当前位一定与前一位结合为两位数，16 //一般情况下答案数目为count[i-2]，当前面只有1位时答案数目为1.17 if(input[i]=='0') {18 if(i==1)19 count[i]=1;20 else21 count[i]=count[i-2];22 } else {23 //当前读取位不为0时，若组成<=26，一般情况下count[i]=count[i-1]+count[i-2]24 //特别注意i=1时，count[i]=225 if( (input[i-1]=='1') || ((input[i-1]=='2')&&(input[i]<='6')) ) {26 if(i==1)27 count[i]=2;28 else29 count[i]=count[i-1]+count[i-2];30 //当前读取位不为0时，若组成>26，count[i]=count[i-1]31 } else {32 count[i]=count[i-1]; 33 }34 35 }36 }37 //count数组中第n位数为最终的答案38 cout << count[n-1] << endl;39 }40 }