# Doubt in SPOJ - ACODE

Ques : ACODE
I am a beginner and I tried to solve this ques using DP .It shows correct results for the testcases not involving zeroes in between the i/p number.
For example)
It fails when i/p is:
310
(shows: 2,but ans should be: 1)
10110
(shows:6,but ans should be:1)

And on submission (when I hadn’t thought about the above test cases) shows TLE.

My code:

#include <iostream>
#include <string.h>
#define ll long long
using namespace std;

ll l; //the size of i/p array

ll func(int *a, int s, int *dp)
{
//Base Case:
if (s >= l)
{
return 1;
}
//DP Case:
if (dp[s] != 0)
{
return dp[s];
}
//Recursive Case:
ll ans = 0;
if (s != l - 1)
{
int dig = a[s] * 10 + a[s + 1];
if (dig > 9 && dig <= 26)
{
ans += func(a, s + 2, dp);
dp[s] = ans;
}
}

ans += func(a, s + 1, dp);
dp[s] = ans;
return ans;
}

int main()
{
string n;
cin >> n;
while (n != "0")
{
l = n.size();
int *a = new int[l];
for (int i = 0; i < l; i++)
{
a[i] = n[i] - '0';
}
int *dp = new int[l]{0};
cout << func(a, 0, dp) << endl;
delete[] dp;
delete[] a;
cin >> n;
}
return 0;
}


@ssrivastava990 @ssjgz @cubefreak777 plzz look into this question

There’s one video for this on Youtube by pepcoding in their dp series
You can refer https://youtu.be/jFZmBQ569So
But their solution is bottom up
but still for intuition you can refer that .

### DP state

DP_i \rightarrow \text{Number of interpretations for a prefix of length $i$}

### Base Case

DP_0=DP_1=1 since there is only one interpretation for prefix of length 1& 0)
→ Question asks us to find DP_N (N is length of string)

### Transitions

DP_i=[S_i \neq0]\times DP_{i-1}+[S_{i-1}S_i \le26 \ \text{and} \ S_{i-1}\neq0]\times DP_{i-2}

1 Like

The code inside for loop is complicated!..

Code
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int

lld n;
lld dp[5001];
string s;
//-4%3=-1

lld fun(int i)
{
int c=(s[i-1]-'0')*10+(s[i]-'0');
if(s[i]!='0')
dp[i]=1;
if(c<=26&&c>9)
dp[i]+=1;

for(int i=2;i<n;i++)
{
c=(s[i-1]-'0')*10+(s[i]-'0');
if(s[i]!='0')
dp[i]+=dp[i-1];
if(c<=26&&c>9)
dp[i]+=dp[i-2];
}
return dp[n-1];
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lld t;
//cin>>t;
string s1="0";
while(1)
{
cin>>s;
if(s==s1)
break;
memset(dp,0,sizeof(dp));
n=s.size();
dp[0]=1;
int res;
if(s.size()>1)
res=fun(1);
cout<<dp[n-1]<<"\n";
//for(int i=0;i<n;i++)
//cout<<dp[i]<<" ";
}
}



Oh…Got it!..Thanks

I think this idea is clear that for each i we have two choices, i.e. either we club up the last 2 indices (i & i-1) and treat them as a single character or we consider only the last letter as a single entity hence DP_i=DP_{i-1}+DP_{i-2} but there are a few edge cases that we need to cover.

1. If S_{i-1}S_i is greater than 26 then we can’t include DP_{i-2} as there’s no character that is assigned a value of 26
2. if S_i=0 then we know that there’s no character which is assigned a value of 0 hence this zero is bound to be used in conjunction with S_{i-1} character to give S_{i-1}S_i=10 or 20 hence we won’t include DP_{i-1} and only include DP_{i-2} (After checking if the value is less than 26 of course)
3. If S_{i-1}=0 then we know that that we must have included S_{i-1} in conjunction with S_{i-2} to make 10 or 20 as discussed in the above point. So we cannot club up S_{i-1} & S_i to make a number like 07 or 08 etc… hence we don’t include DP_{i-2}.
code
#include "bits/stdc++.h"
using namespace std ;

int main(){
string s   ;
cin>>s  ;
while(s!="0"){
int n = s.size() ;
vector<int>dp(n+1) ;
dp[0]=dp[1]=1;
for(int i=2;i<n+1;i++){
int d = 10*(s[i-2]-'0')+s[i-1]-'0' ; // S_{i-1}S_i
if(s[i-1]!='0')
dp[i]+=dp[i-1] ;
if(d<=26&&s[i-2]!='0')
dp[i]+=dp[i-2] ;
}
cout << dp[n] << '\n' ;
cin>>s  ;
}
}


Nicely explained!..Thanks