tips on memo

memo

#first
#- write recursive solution
coins = [50, 20, 10, 5, 1]
count =0
count2 = 0
def cc(a,d):
    global count
    count+=1
    if a <0 or d == 0:
        return 0
    elif a == 0:
        return 1
    else:
        return cc(a-coins[d-1],d) + cc(a,d-1)
#second
#- copy over and change to memo
coins = [50, 20, 10, 5, 1]
count =0
count2 = 0
def cc(a,d):
    global count
    count+=1
    if a <0 or d == 0:
        return 0
    elif a == 0:
        return 1
    else:
        return cc(a-coins[d-1],d) + cc(a,d-1)
#third
#- create dictionary to keep track
#- check dict before compute
#- instead of returning ans, put the ans into dict before return
seen = {}
def memo_cc(a, d):
    if (a, d) in seen:
        return seen[(a, d)]
    if a < 0 or d == 0:
        ans = 0
    elif a == 0:
        ans = 1
    else:
        ans = memo_cc(a-coins[d-1], d) + memo_cc(a, d-1)
        seen[(a, d)] = ans
        return ans