 # SPOJ.com - Problem ACODE

I am solving alpha code on spoj.I wrote the below code and it is give wrongans for the sample test case.Please teach me how to solve the problem using recursion only.Thanks
``````def issafe(pos):
global n
if pos+1<n:
return True
return False

def solve(pos,st):
global n
if pos>n-1:
return 0
z=0
if issafe(pos):
z=st[pos]*10+st[pos+1]
x=0
if st[pos]<=26:
x=1+solve(pos+1, st)
y=0
if z>=10 and z<=26 :
y=1+solve(pos+2, st)
return x+y
while(True):
nt=input()
n=len(nt)

if nt=='0':
break
st=[]
for i in nt:
st.append(int(i))

ans=solve(0, st)
print(ans)``````

i don’t think it can be solved using recursion, u need dp for this

I think he meant recursion with memoization

Why it cant be solved using recursion?Thanks

see, the basic procedure is to use a for loop, so recursion can be used, but i don’t think just a recursive approach will help you with this.
Consider the case 11
Number of ways to represent 11 is 2: AA and K. But your code is printing 3. That’s because you are adding 1 to the count every time you call the function.
what you have to do is for every i in string s, if s[i]!=‘0’, count[i]=1(count gives number of possibilities at that index)
now, there are cases where 2 characters can be used to represent an alphabet, so, we need to add all such cases together(in above example 11) hence we add count[i-2] to count[i]
why i-2? because after i-2, the i-1th character and i th character form the new alphabet, so its a new arrangement added to all the previous arrangements.
take another example 111
here c=1 c=1+1 c=1+2…hence ans is 3
for dual possibilities such as this right at the first index, i would advise u to add a space in front of the string ie ‘111’ -> ’ 111’

if you find it to be unclear(well because i am not that good at explaining things) you can use this link for further reference-https://www.quora.com/How-do-I-solve-the-ACODE-problem-on-SPOJ

Actually I want to solve it using recursion + memoisation.I never used bottom up dp approach.