def choose(n, k):
    '''Computes the binomial coefficient C(n, k) naively.'''
    if k == 0 or k == n:
        return 1
    else:
        return choose(n-1, k-1) + choose(n-1, k)

def memchoose(m, p):
    '''Computes the binomial coefficient C(n, k) by memoization.'''
    table =  [[None]* (p+1) for i in range(m+1)]
    def choose(n, k):
        if table[n][k] == None:
            if k == 0 or n == k:
                table[n][k] = 1
            else:
                table[n][k] = choose(n-1, k-1) + choose(n-1, k)
        return table[n][k]
    return choose(m, p)

def monica_dpchoose(m, p):
    '''Computes the binomial coefficient C(n, k) by dynamic programming.
       Table filling is done column-by-column.

       Author: Monica Klutzke
    '''
    table =  [[None]* (p+1) for i in range(m+1)]
    for k in range(p+1):
        for n in range(k, m+1):
            if k == 0 or n == k:
                table[n][k] = 1
            else:
                table[n][k] = table[n-1][k-1] + table[n-1][k]       
    return table[m][p]

def dpchoose(m, p):
    '''Computes the binomial coefficient C(n, k) by dynamic programming.
       Table filling is done row-by-row.  Apparent space waste is also
       avoided.'''
    table =  [None] * (m+1)
    for n in range(m+1):
        table[n] = [None] * (min(n, p)+1)
        for k in range(min(n, p)+1):
            if k == 0 or n == k:
                table[n][k] = 1
            else:
                table[n][k] = table[n-1][k-1] + table[n-1][k]       
    return table[m][p]

def dmemchoose(m, p):
    '''Computes the binomial coefficient C(n, k) by memoization and
    using a dictionary as a table.'''
    table = {}
    def choose(n, k):
        if (n, k) not in table:
            if k == 0 or n == k:
                table[n, k] = 1
            else:
                table[n, k] = choose(n-1, k-1) + choose(n-1, k)
        return table[n, k]
    return choose(m, p)

def ddpchoose(m, p):
    '''Computes the binomial coefficient C(n, k) by dynamic programming.
       Table filling is done row-by-row.  Apparent space waste is also
       avoided. This version uses a dictionary as a table.'''
    table = {}
    for n in range(m+1):
        for k in range(min(n, p)+1):
            if k == 0 or n == k:
                table[n,k] = 1
            else:
                table[n,k] = table[n-1,k-1] + table[n-1,k]       
    return table[m,p]

#print choose(30, 17) # gives 119759850
print memchoose(30, 17), monica_dpchoose(30, 17), dpchoose(30, 17), dmemchoose(30, 17), ddpchoose(30,17)