Maximum Coins in Grid

Medium
Matrix Dynamic Programming Algorithm
🏢Zillow
0 views0 likes

Problem Description

Maximum Coins in Grid

Given a 2D matrix where each cell represents the number of coins in that cell, determine the maximum number of coins you can collect starting from the top-left corner (matrix[0][0]) and moving only to the right or down, reaching the bottom-right corner of the matrix.

Write a function that takes a 2D matrix as input and returns the maximum number of coins collected.

Example 1: 

Input: [[0, 3, 1, 1], [2, 0, 0, 4], [1, 5, 3, 1]]
Output: 12
Explanation: The path 0 → 2 → 1 → 5 → 3 → 1 collects the maximum coins (0 + 2 + 1 + 5 + 3 + 1 = 12).

Example 2: 

Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: 29
Explanation: The path 1 → 2 → 3 → 6 → 9 collects the maximum coins (1 + 2 + 3 + 6 + 9 = 21).

Constraints:

  • The matrix dimensions are m x n.
  • Each cell contains a non-negative integer.

Hints

Use dynamic programming to keep track of the maximum coins collected up to each cell.

Initialize the DP table with the same dimensions as the matrix.

For each cell, the value in the DP table will be the coin count of that cell plus the maximum of the values from the cell directly above or to the left.

Solution