I am not sure why this code is not working.
If you do forward DP it works while in reverse case it does not work . why??
I am tired of getting WAs
#include <iostream>
#include <algorithm>
#include <string>
#include <conio.h>
using namespace std;
/*
* My method for solving
* T(n) = T(n-1) + T(n-2)
* provided both the T(n-1) and T(n-2) are possbile
* so for the last digit it is just 1
*/
int main()
{
char digits[5005];
scanf("%s",&digits);
// getline(cin,digits);
while(strcmp(digits,"0") != 0)
{
long long int res[5005];
int c=0;
int len = strlen(digits);
//res[digits.length()-1] = 0;
res[len] = 0;
res[len+1] = 0;
res[len-1] = 1;
res[len-2] = 1;
for(int i=len-2;i>=0;i--)
{
res[i] = 0;
if(digits[i]>='1' && digits[i]<='9')
{
res[i] = res[i+1];
}
long long int val = (digits[i]-'0')*10+digits[i+1]-'0';
if(val <= 26 && val>=10)
{
res[i] += res[i+2];
if(i+2==len)
res[i] += 1;
}
else if(digits[i]=='0'){}
}
/*if(digits[digits.length()-1]!='0')
res[digits.length()-1] = 1;
else if(digits[digits.length()-1]=='0' && digits.length()==1)
{res[0] = 0;break;}
res[digits.length()-2] = 1;
for(long int i=digits.length()-2;i>=0;i--)
{
//res[i] = 0;
if(digits[i] == '1' || digits[i] == '2')
{
if(digits[i+1]=='0')
{
if(i+2<digits.length())
res[i] = res[i+2];
else
res[i] = 1;
}
else if (((digits[i]-'0')*10) + digits[i+1]-'0'> 26)
{
res[i] = res[i+1];
}
else
{
if(i+2<digits.length())
res[i] = res[i+1]+res[i+2];
else
res[i] = res[i+1]+1;
}
}
else if(digits[i]=='0')
{
res[0] = 0;
break;
}
else
res[i] = res[i+1];
*/
/* //for n-1 thing
if(digits[i] >= '1' && digits[i]<='9')
res[i] = res[i+1];
//for the n-2 thing
char str[3];
str[0] = digits[i];str[1] = digits[i+1];str[2] = '\0';
int dig2 = atoi(str);
// cout<<dig2<<endl;
if(dig2>=10 && dig2<=26)
{
if(i==digits.length()-2)
{
res[i] = res[i+1]+1;
}
else
res[i] = res[i] + res[i+2];
}
else
res[i-1] = res[i+1];
//taking care of the zero
// cout<<"char at "<<i<<" is "<<digits[i]<<endl;
// cout<<"res at "<<i<<" is " <<res[i]<<endl;
*/
// if()
printf("%d\n",res[0]);
//cout<<res[0]<<endl;
//getline(cin,digits);
scanf("%s",&digits);
}
}