Binarysearch.io Collecting Coins Solution

January 03, 2021

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.

Problem Link

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)