Problem

You are given a 2-d 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.

Examples

Example 1

$$ \begin{array}{|c|c|c|c|} \hline \colorbox{green}0 & 3 & 1 & 1 \\ \hline \colorbox{green}2 & 0 & 0 & 4 \\ \hline \colorbox{green}1 & \colorbox{green}5 & \colorbox{green}3 & \colorbox{green}1 \\ \hline \end{array} $$

1
2
3
4
5
6
7

Input: matrix = [
	[0, 3, 1, 1],
	[2, 0, 0, 4],
	[1, 5, 3, 1]
]
Output: 12
Explanation: The most we can collect is 0 + 2 + 1 + 5 + 3 + 1 = 12 coins.

Solution

Method 1 - DP

To achieve the maximum number of coins, use dynamic programming to keep track of the maximum coins collected up to each cell. For each cell, the maximum coins collected will be the maximum of coins collected from the cell above it or the cell to the left of it plus the coins in the current cell.

Approach

  1. Create a DP table (dp) of the same dimensions as the input matrix.
  2. Initialize dp[0][0] to matrix[0][0] since that’s the starting point.
  3. Fill in the first row and first column of the DP table since movements are restricted to right or down.
  4. For each remaining cell (i, j), compute the maximum coins collected by considering either coming from the top (dp[i-1][j]) or from the left (dp[i][j-1]), and add the coins in the current cell.
  5. The value at dp[m-1][n-1] (bottom-right corner) will give the maximum number of coins collected.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class Solution {
    public int maxCoins(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        
        dp[0][0] = matrix[0][0];

        // Initialize first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
        }

        // Initialize first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }

        // Fill the rest of the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = matrix[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] matrix = {
            {0, 3, 1, 1},
            {2, 0, 0, 4},
            {1, 5, 3, 1}
        };
        System.out.println(solution.maxCoins(matrix)); // Output: 12
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def maxCoins(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0]*n for _ in range(m)]
        
        dp[0][0] = matrix[0][0]

        # Initialize first row
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + matrix[0][j]

        # Initialize first column
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + matrix[i][0]

        # Fill the rest of the dp table
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = matrix[i][j] + max(dp[i - 1][j], dp[i][j - 1])

        return dp[m - 1][n - 1]

# For testing the solution
if __name__ == "__main__":
    solution = Solution()
    matrix = [
        [0, 3, 1, 1],
        [2, 0, 0, 4],
        [1, 5, 3, 1]
    ]
    print(solution.maxCoins(matrix))  # Output: 12

Complexity

  • ⏰ Time complexity: O(m * n) where m is the number of rows and n is the number of columns.
  • 🧺 Space complexity: O(m * n) for the DP table.