Hey guys,
I've tried out the test cases here (and they work fine for me), but I just can't seem to get AC. I've used forward DP. Any help?
#include<stdio.h>
#include<string.h>
int valid;
long long int dp[10000];
int count(char str[],int len)
{
memset(dp,0,sizeof(dp));
int i;dp[0]=1;
for(i=1;i<len;i++) {
//if(str[i]=='0')
dp[i]=dp[i-1];
//else
{ if(str[i-1]=='1')
{ if(dp[i-1]==1 && str[i]!='0')
dp[i]=2;
else if(str[i]!='0')
dp[i]=dp[i-1]+dp[i-2];
}
if(str[i-1]=='2' && (str[i]>='0' && str[i]<='6')) {
if(dp[i-1]==1 && str[i]!='0')
dp[i]=2;
else if(str[i]!='0')
dp[i]=dp[i-1]+dp[i-2];
}
}
}
/* for(i=0;i<len;i++)
printf("%d ",dp[i]);
printf("\n");
*/ return dp[len-1];
}
int main()
{
while(1) {
char str[5010];
scanf("%s",str);//cout<<str<<endl;
if(strcmp("0",str)==0)
return 0;
printf("%d\n",count(str,strlen(str)));
valid=0;
}
return 0;
}