Q:

Pascal's triangle with memoization

Problem:

Pascal’s triangle is a useful recursive definition that tells us the
  coefficients in the expansion of the polynomial (x + a)^n. Each
  element in the triangle has a coordinate, given by the row it is on
  and its position in the row (which you could call its column). Every
  number in Pascal’s triangle is defined as the sum of the item above it
  and the item that is directly to the upper left of it. If there is a
  position that does not have an entry, we treat it as if we had a 0
  there. Below are the first few rows of the triangle:
Item:   0  1  2  3  4  5

Row 0:  1

Row 1:  1  1

Row 2:  1  2  1

Row 3:  1  3  3  1

Row 4:  1  4  6  4  1

Row 5:  1  5 10 10  5  1

...

Define the procedure pascal(row, column) which takes a row and a
  column, and finds the value at that position in the triangle. Don’t
  use the closed-form solution, if you know it.

Solution:
def pascal_with_memoization(row, column):
    """
    >>> pascal_with_memoization(3, 2)
    3
    >>> pascal_with_memoization(3, 3)
    1
    >>> pascal_with_memoization(5,4)
    5
    """
    cache = {}
    for row_indx in range(0, row + 1):
        cache.setdefault(row_indx, []).insert(0, 1)
    for col_indx in range(1, column + 1):
        cache.setdefault(0, []).insert(col_indx, 0) 
    def pascal(row, column):
        if column == 0:
            return cache[row][column]
        elif row  == 0:
            return  cache[row][column]
        else:
            value_1 = 0
            value_2 = 0
            lst = cache[row-1]
            if len(lst) > column: 
                value_1 = cache[row-1][column]
                value_2 = cache[row-1][column-1]
            elif len(lst) > column - 1:
                value_1 = pascal(row-1, column)
                value_2 = cache[row-1][column-1]  
                cache.setdefault(row-1, []).insert(column, value_1)
            else:
                value_1 = pascal(row-1, column)
                value_2 = pascal(row-1, column-1)
            return value_1 + value_2
    return pascal(row, column)

Can we improve the memoized code?

A:

The canonical way to memoize Python code is with a decorator, for example:
from functools import wraps

def memoize(func):
    @wraps(func)
    def wrapper(*args):
        if args not in wrapper.cache:
            wrapper.cache[args] = func(*args)
        return wrapper.cache[args]
    wrapper.cache = {}
    return wrapper

(functools.wraps is to handle the name of and any docstrings on the memoized function). Within the function itself, you don't need to refer to the cache at all; you simply make a recursive call and let the decorator handle the caching. This makes your code much easier to read and write, because the only difference is:
@memoize  # a single line
def pascal(row, column):
    if row < 0 or column < 0 or column > row:
        raise ValueError
    if column == 0 or column == row:
        return 1
    return pascal(row-1, column) + pascal(row-1, column-1)

You can see the cache fill up as you use the function:
>>> pascal.cache
{}
>>> pascal(4, 3)
4
>>> pascal.cache
{(3, 2): 3, (3, 3): 1, (2, 1): 2, (4, 3): 4, (2, 2): 1, (1, 0): 1, (1, 1): 1}

