Dynamic Programming For Primitive Calculator

I'm dealing with the problem, that is pretty similar to change coins problem. I need to implement a simple calculator, that can perform the following three operations with the curr

Solution 1:

Just solve it with a simple recursion and Memoization:

Code:

d = {}

deff(n):
    if n == 1:
        return1, -1if d.get(n) isnotNone:
        return d[n]
    ans = (f(n - 1)[0] + 1, n - 1)

    if n % 2 == 0:
        ret = f(n // 2)
        if ans[0] > ret[0]:
            ans = (ret[0] + 1, n // 2)

    if n % 3 == 0:
        ret = f(n // 3)
        if ans[0] > ret[0]:
            ans = (ret[0] + 1, n // 3)

    d[n] = ans
    return ans

defprint_solution(n):
    if f(n)[1] != -1:
        print_solution(f(n)[1])
    print n,

defsolve(n):
    print f(n)[0]
    print_solution(n)
    print''

solve(10)

Hint: f(x) returns a tuple (a, b), which a denotes the minimum steps to get x from 1, and b denotes the previous number to get the optimum solution. b is only used for print the solution.

Output:

4 # solution for 10
1 3 9 10 

7 # solution for 111
1 2 4 12 36 37 111

You may debug my code and to learn how it works. If you are beginner at DP, you could read my another SO post about DP to get a quick start.

---

Since Python can't recurse a lot (about 10000), I write an iterative version:

# only modified function print_solution(n) and solve(n)defprint_solution(n):
    ans = []
    while f(n)[1] != -1:
        ans.append(n)
        n = f(n)[1]
    ans.append(1)
    ans.reverse()
    for x in ans:
        print x,

defsolve(n):
    for i inrange(1, n):
        f(i)[0]
    print_solution(n)
    print''

solve(96234) # 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234