i dont know wat is wrong..... i have taken into account zeros also
here is the code..... i am new to dp so plz help..
[code]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 5000
char str[5000];
long long s[5000];
long long dps(char *str)
{
int i;
/* if(strlen(str)==1) return 1;
if(strlen(str)==2){
if(str[0]=='1') return 2;
else if(str[0]=='2' && str[1]<='6') return 2;
else return 1;
}
*/
int len=strlen(str);
s[0]=1;
if(str[0]=='1'&&str[1]!='0') s[1]=2;
else s[1]=1;
if(str[0]=='2'&& str[1]<='6'&&str[1]!='0') s[1]=2;
else s[1]=1;
if(str[0]=='2'&& str[1]>'6') s[1]=1;
if(str[0]>'2') s[1]=1;
for(i=2;i<len;i++){
if(str[i-1]!=0 && str[i-1]=='2' && str[i]!='0' && str[i]<='6')
s[i]=s[i-1] +s[i-2];
if(str[i-1]=='1')
s[i]=s[i-1] +s[i-2];
if(str[i-1]>'2'||str[i-1]=='0'||str[i]=='0') //251
s[i]=s[i-1];
}
return s[len-1];
}
int main()
{
scanf("%s",str);
do{
printf("%lld",dps(str));
scanf("%s",str);
}while(str[0]-'0'!= 0);
return 0;
}
[/code]