ACODE spoj problem solution(Alphacode)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

HII ............... TYPE: a nice DP LOGIC:: Here it is clear that the solution of subproblem must require to solve the solution of original problem............. So just think that how to calculate the solution for string of length(1,2,3) then i m sure u will get that how to use solution of subproblem....... MY AC C++ SOLUTION IS::: #include<bits/stdc++.h> using namespace std; int main() { while(1) { char str[5010]; scanf("%s",str); if(str[0]=='0') break; unsigned long long int dp[5010]; long long int len=strlen(str); memset(dp,0,5010); dp[0]=1; long long int x,i; for(i=1;i<=len-1;i++) { x=(str[i-1]-'0')*10+(str[i]-'0'); if(str[i]-'0') dp[i]=dp[i-1]; if(x>=10 && x<=26) dp[i]+=dp[(i-2)<0?0:i-2]; } printf("%llu\n",dp[len-1]); } return 0; }