POJ 2033 Alphacode

問題

アルファベット大文字からなる平文に対し、A=1、B=2、…、Z=26と置き換える暗号化を行う。この暗号文は一意に復号化できない可能性がある。暗号文が与えられるので何通りの復号化があるか求めよ。

やりかた

DP。
dp[i]:=（i桁目までの復号化パターン数）とすると、今見ている桁だけ使った置換と、一つ前の桁も使った置換がありうるのでそれらの和になる。
dp[i + 1] = dp[i] + dp[i - 1]
ただし、今見ている桁が0の場合と、一つ前の桁が0の場合は例外なので注意。
以下ソース。

int main(int argc, char **argv){
  string s;
  while(cin >> s){
    if(s == "0") break;
    
    ll dp[1000000];
    FILL(dp, 0);
    dp[0] = 1;
    for(int i = 0; i < s.size(); i++){
      //今見ている桁だけ使った置換
      if(s[i] != '0') dp[i + 1] += dp[i];
      //一つ前の桁も使った置換が可能な場合
      if(i - 1 >= 0 && (s[i - 1] - '0' != 0) && 
	 (s[i] - '0') + 10 * (s[i - 1] - '0') <= 26)
	dp[i + 1] += dp[i - 1];
    }
    cout << dp[s.size()] << endl;
  }
  return 0;
}