http://www.spoj.com/problems/ACODE/

ACODE - Alphacode.cpp

#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 5005;
const int OO = 1e9;


string s;
int n;
ll cache[MAX];

ll acode(int i) {
    if(i == n)
        return 1;
    ll &ret = cache[i];
    if(ret != -1)
        return ret;
    ret = 0;
    if(s[i] != '0') {
        ret += acode(i+1);
        if(i!=n-1) {
            int x = (s[i]+'\0'-48) * 10;
            int y = s[i+1]+'\0'-48;
            //cout << x+y << endl;
            if(x+y <= 26)
                ret += acode(i+2);
        }
    }

    return ret;
}

int main() {
    while(cin>>s && s != "0") {
        clr(cache, -1);
        n = s.length();
        cout << acode(0) << endl;
    }
    return 0;
}