Q: Dynamic Programming: Smallest cost path through matrix -- memoization? Is there a simple way to memoize results? my dynamic programming solution is potentially calling the same function, with the same parameters, multiple times.
I think memoizing would add speed. However, I'm not sure what the best approach is.
Here's the original function, which works, albeit, it's not memoized:
def dim(M):
    rows = len(M)
    cols = len(M[0])
    return rows, cols

def minimumCostPath(matrix, i=0, j=0, total=0):
    r,c = dim(matrix)
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        return min(minimumCostPath(matrix, i+1, j, total+down),
                    minimumCostPath(matrix, i, j+1, total+right))
    elif i+1 < r:
        right = matrix[i+1][j]
        return minimumCostPath(matrix, i+1, j, total+right)
    elif j+1 < c: 
        down = matrix[i][j+1]
        return minimumCostPath(matrix, i, j+1, total+down)
    else:
        return total + matrix[0][0]       

test = [ [23,70,54], 
         [86,5,13], 
         [86,62,77], 
         [60,37,32], 
         [88,58,98] ]
total = minimumCostPath(test)
>>>
318

Below is my attempt to memoize this function with a matrix (nested list) of zeros.
def solution(matrix):
  cache = [[0 for j in range(len(matrix[0]))] for i in range(len(matrix))] 
  return helper(matrix, cache, i=0, j=0, total=0) 

def helper(matrix, cache, i=0, j=0, total=0):
    r,c = dim(matrix)
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        
        if cache[i+1][j] > 0:
          go_down = cache[i+1][j] + down
        else:
          go_down = helper(matrix, cache, i+1, j, total+down)
          cache[i+1][j] = go_down
        
        if cache[i][j+1] > 0 :
          go_right = cache[i][j+1] + right
        else:
          go_right = helper(matrix, cache, i, j+1, total+right)
          cache[i][j+1] = go_right 
        
        return min(go_down, go_right)
    elif i+1 < r:
        down = matrix[i+1][j]
        if cache[i+1][j] > 0:
          go_down = cache[i+1][j] + down
        else:
          go_down = helper(matrix, cache, i+1, j, total+down)
          cache[i+1][j] = go_down  
          return go_down     
    
    elif j+1 < c: 
        right = matrix[i][j+1]
        if cache[i][j+1] > 0 :
          go_right = cache[i][j+1] + right
        else:
          go_right = helper(matrix, cache, i, j+1, total+right)
          cache[i][j+1] = go_right         
        return go_right
    
    else:
        return total + matrix[0][0]


solution(test)

Two problems.

*

*I'm getting an error, TypeError: '<' not supported between instances of 'NoneType' and 'int' line 23 is evaluating either go_right or go_down as None, which is peculiar.

*It's not very succinct or pretty. Perhaps a better helper function would simplify the code.

Lastly, I do understand that there is the bottom-up approach, which does not use recursion but rather fills in table cells, iteratively. At this point, I'm wondering how the recursive solution could leverage memoization, not start from scratch on bottom up implementation.

A: Firstly, your bug: in one of the branches, return go_down is indented too far, so the non-recursive calculation of go_down won't return the value; instead, it'll fall off the end of the function and return the implicit None
As far as memoization is concerned, there are cache and lru_cache decorators in functools. Last I used it (about 5 years and many versions ago) it was a bit slow, only really useful for external data (disk or network); you'll have to measure whether it performs satisfactorily for you. It's probably improved a lot since then.
If you do need to implement a cache manually (if the functools.cache decorator proves to be too slow), a pattern with the caching separate is probably better, to avoid mixing of concerns:
minimumCostPath_cache = {}

def minimumCostPath(matrix, i=0, j=0):
    try:
        return minimumCostPath_cache[i, j]
    except KeyError:
        result = minimumCostPath_cache[i, j] = minimumCostPath_raw(matrix, i, j)
        return result

def minimumCostPath_raw(matrix, i=0, j=0):
   ...

To avoid global variables and calls with different matrices interfering with each other, you might do this in a class:
class MinimumCostPath:
    def __init__(self, matrix):
        self.cache = {}
        self.matrix = matrix

    def calculate(self, i=0, j=0):
        try:
            return self.cache[i, j]
        except KeyError:
            result = self.cache[i, j] = self.calculate_uncached(i, j)
            return result

    def calculate_uncached(self, i=0, j=0):
        ...


A: If you have Python 3.9, get to know the @cache decorator in order to achieve worry free memoization
@cache
def factorial(n):
    return n * factorial(n-1) if n else 1

>>> factorial(10)      # no previously cached result, makes 11 recursive calls
3628800
>>> factorial(5)       # just looks up cached value result
120
>>> factorial(12)      # makes two new recursive calls, the other 10 are cached
479001600

source: https://docs.python.org/3/library/functools.html

A: from functools import lru_cache
@lru_cache(maxsize=None, typed=False)
def minimumCostPath(matrix, i=0, j=0):
    r,c = len(M), len(M[0])
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        return min(minimumCostPath(matrix, i+1, j) + down,
                    minimumCostPath(matrix, i, j+1) + right)
    elif i+1 < r:
        right = matrix[i+1][j]
        return minimumCostPath(matrix,i+1, j) + right
    elif j+1 < c: 
        down = matrix[i][j+1]
        return minimumCostPath(matrix,i, j+1) + down
    else:
        return matrix[0][0]

Moved the total parameter out and used lru_cache to save previous function calls. It had 8 hits, 15 misses and current size 15.
