Unique paths using memoization

unique_paths_memoization.py

#!/usr/bin/env python

m = 3
n = 4

S = [[None for _ in range(n+1)] for _ in range(m+1)]

def explore(i, j):
  if i < 0 or j < 0 or i > m or j > n:
    return 0

  if i==0 and j==0:
    return 1

  if S[i][j] is not None:
    return S[i][j]

  S[i][j] = explore(i-1, j) + explore(i, j-1)
  return S[i][j]

n_paths = explore(m-1, n-1)
print(f"Number of unique paths: {n_paths}")