Dynamic Programming for the number of ways of climbing steps

Question

The question is to write a function using dynamic programming for the number of ways to climb N steps. Given that only 1 step or 2 steps can be climbed at a time.

For example, if N=3, the function should return [(1,1,1),(1,2),(2,1)]. I've written a code in python 3 to calculate. The code is working fine but as N gets as large as 40 it takes the same time or the spyder(Anaconda) application crashes when compared to the same recursive code without using dynamic programming.

Shouldn't it be way more efficient than the normal one?

I've attached the DP code below

def stepsdyn(N,memo={}):
    """
    L1 is the list of all possibilities in the left side of the search tree,
    that is with 1 as the last element
    L2 is the list of all possibilities in the right side of the search tree
    memo stores the results of corresponding N
    returns memo[N]
    """
    L1=[]
    L2=[]
    if N==1:
        return [(1,)]
    elif N==0:
        return [()]
    else:
        try:
             return memo[N]
        except:
             for items in stepsdyn(N-1,memo):
                 items+=(1,)
                 L1.append(items)
             for items in stepsdyn(N-2,memo):
                 items+=(2,)
                 L2.append(items)
             memo[N]=L1+L2
             return memo[N] 

Answer 1

Basic idea

In computer programming the most basic and common tradeoff is the one between time efficiency and space efficiency. Memoization can be good for time but bad for space and that is the case here. Your program is crashing because that memoization dictionary is holding a lot of data. Right off the bat your recurrence relation means you never need the data that is being held in the N - 3 spot so you can get rid of it. This somewhat alleviates the memory burden (but not by much).

Problems/concerns with code

1. Don't memoize values you don't need (see above).
2. Python's handling of mutable default argument means the memo dict is only created once. See this SO post for more details. This also means that the dictionary is sitting around (in memory) after the function returns... not good. Generally don't use mutable default arguments unless you have a compelling reason.
3. list comprehensions can be a bit faster than explicit for loops. More importantly in this case, they are more readable.
4. This last one is more a style thing. You are adding the 1 or the 2 to the tail of the items returned from the recursive call. Typically those elements are added at the head.

Solutions

Same algorithm but more memory and time efficient

def stepsdyn_new(N, memo):
    try:
        return memo[N]
    except KeyError:
        l1 = [(1,) + items for items in stepsdyn_new(N - 1, memo)]
        l2 = [(2,) + items for items in stepsdyn_new(N - 2, memo)]
        memo.pop(N - 2)
        memo[N] = l1 + l2
        return memo[N]

Note: I pass the base cases in as an argument, but you can add the original if/else if desired.

Returning strings

def stepsdyn_str(N, memo):
    try:
        return memo[N]
    except KeyError:
        l1 = ['1' + x for x in stepsdyn_str(N - 1, memo)]
        l2 = ['2' + x for x in stepsdyn_str(N - 2, memo)]
        memo.pop(N - 2)
        memo[N] = l1 + l2
        return memo[N]

This will return a list of string (e.g. ['111', '12', '21']) instead of a list of tuples. Because each character in a python string only uses 1 byte (instead of the 8 bytes per element in a list/tuple) this yields a lot of memory savings. The result can be converted back to a list of tuples with the following code (though this would incur additional speed/memory penalties):

[tuple(map(int, tuple(x))) for x in stepsdyn_str(N, {0: [''], 1: ['1']})]

Efficiency

Note: the steps function is a non-memoized solution (included below for completeness).

Speed

|--------------|----------------------------|----------------------------|
|              |           N = 20           |           N = 33           |
|--------------|----------------------------|----------------------------|
| steps        | 47 ms ± 7.34 ms per loop   | 41.2 s ± 1.6 s per loop    |
|--------------|----------------------------|----------------------------|
| stepsdyn     | 10.1 ms ± 1.23 ms per loop | 9.46 s ± 691 ms per loop   |
|--------------|----------------------------|----------------------------|
| stepsdyn_new | 6.74 ms ± 1.03 ms per loop | 7.41 s ± 396 ms per loop   |
|--------------|----------------------------|----------------------------|
| stepsdyn_str | 3.28 ms ± 68.8 µs per loop | 3.67 s ± 121 ms per loop   |
|--------------|----------------------------|----------------------------|

Obtained using:

%timeit steps(N)
%timeit stepsdyn(N, memo={})
%timeit stepsdyn_new(N, {0: [()], 1: [(1,)]})
%timeit stepsdyn_str(N, {0: [''], 1: ['1']})

Memory

These estimates are specific to my 16GB memory MBP while evaluating the functions for N=33:

• steps: 10.8% max memory
• stepsdyn: 22.0% max memory
• stepsdyn_new: 15.7% max memory
• stepsdyn_str: 3.6% max memory

Non-memoized solution

def steps(N):
    if N == 0:
        return [()]
    elif N == 1:
        return [(1,)]
    else:
        l1 = [(1,) + items for items in steps(N - 1)]
        l2 = [(2,) + items for items in steps(N - 2)]
        return l1 + l2

Answer 2

If you'd like a succinct way to just count the number of ways to climb N steps, given that only 1 step or 2 steps can be climbed at a time, we could implement something like this:

def f(n):
  a, b = 0, 1

  for i in xrange(n):
    a, b = b, a + b

  return b

Output:

   f(3)
=> 3
   f(5)
=> 8
   f(40)
=> 165580141
   f(120)
=> 8670007398507948658051921L

Notice that the result is simply the (n + 1)th Fibonacci number.