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[0]=1 c[1]=1+1 c[2]=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.