poj2033

递推

#include <cstdio>
#include <cstring>

char st[50005];
int f[50005];

bool ok(char a, char b)
{
    if (a == '0')
        return false;
    int x = (a - '0') * 10 + b - '0';
    return x <= 26;
}

int main()
{
    while (scanf("%s", st), st[0] != '0')
    {
        int len = strlen(st);
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <= len; i++)
            if (st[i - 1] == '0')
                f[i] = f[i - 2];
            else if (ok(st[i - 2], st[i - 1]))
                f[i] = f[i - 1] + f[i - 2];    
            else
                f[i] = f[i - 1];
        printf("%d\n", f[len]);
    }
    return 0;
}