Problem statement
You are given a two-dimensional integer matrix where each cell represents number of coins in that cell. Assuming we start at matrix[0][0], and can only move right or down, find the maximum number of coins you can collect by the bottom right corner.
Intuition
The key idea is that every step i.e. (i, j) we have a choice wether to go right, i.e. (i+1, j) or to go bottom (i, j+1). We use that to come up with a recursive formulation:
optimal_path(i, j) = matrix[i][j] + max(optimal_path(i+1, j), optimal_path(i, j+1))
Following is the naive recursive code:
Recursive code
def solve(self, matrix):
M, N = len(matrix), len(matrix[0])
def optimal_path(i, j):
if i >= M or j >= N: return 0
return matrix[i][j] + max(optimal_path(i + 1, j), optimal_path(i, j + 1))
return optimal_path(0, 0)Implementation
Memoized code
def solve(self, matrix):
M, N = len(matrix), len(matrix[0])
memo = {}
def optimal_path(i, j):
if (i, j) in memo:
return memo[(i, j)]
if i >= M or j >= N:
return 0
output = matrix[i][j] + max(optimal_path(matrix, i + 1, j), optimal_path(matrix, i, j + 1))
memo[(i, j)] = output
return output
return optimal_path(0, 0)Top-Down Dynamic Programming
def solve(self, matrix):
M, N = len(matrix), len(matrix[0])
dp = [[0]*(N+1) for i in range(M+1)]
for i in range(1, M+1):
for j in range(1, N+1):
dp[i][j] = matrix[i-1][j-1] + max(dp[i-1][j], dp[i][j-1])
return dp[M][N]Time complexity
O(N**2) for the memoized and dynamic programming solutions
Space complexity
O(N**2)