# 题目

## 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.

25114
1111111111
3333333333
0

6
89
1

# 题解

dp[i] 表示到第 i 个字符的可能个数

• 如果第 i 个数可以和第 i-1 个数连起来构成一个合法的数( 1~26 )
那么,它有两种计算情况:

• 不和前面的数连起来,将他单独看作一个数,有 dp[i-1] 种可能

• 和前面的数连起来,共同构成一个数
这与上一个数( i-1 )单独看作一个数的数量一样,即 dp[i-2]

• 如果第 i 个数不能和第 i-1 个数连起来构成一个合法的数
那么,显然只有一种情况,就是将第 i 个数,单独看成一个,也即 dp[i] = dp[i-1]

# 代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 50005;
char s[maxn];
int dp[maxn];
int ss[maxn];

bool Do() {
scanf("%s",s);
if(s[0] == '0')
return false;
int len = strlen(s);

int pos = 1;
for(int i = 0;i < len;i++) {
ss[pos] = s[i] - '0';
if(ss[pos] == 0) {
ss[pos - 1] = ss[pos - 1] * 10 + ss[pos];
} else {
pos++;
}
}

memset(dp,0,sizeof(dp));
dp[0] = dp[1] = 1;

for(int i = 2;i < pos;i++) {
int num = ss[i - 1];
int k = ss[i];
while(k) {
num *= 10;
k /= 10;
}
num += (ss[i]);

if(num <= 26)
dp[i] = dp[i - 1] + dp[i - 2];
else
dp[i] = dp[i - 1];

}

printf("%d\n",dp[pos - 1]);

return true;
}

int main() {
while(Do());
return 0;
}