DEV Community 👩‍💻👨‍💻

Wenqi Jiang
Wenqi Jiang

Posted on

Collecting Coins

Description

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.

Constraints:

  • n, m ≤ 100 where n and m are the number of rows and columns in matrix.

Example 1

Input

matrix = [
    [0, 3, 1, 1],
    [2, 0, 0, 4]
]
Enter fullscreen mode Exit fullscreen mode

Output

9
Enter fullscreen mode Exit fullscreen mode

Explanation

We take the following path: [0, 3, 1, 1, 4]
Enter fullscreen mode Exit fullscreen mode

Example 2

Input

matrix = [
    [0, 3, 1, 1],
    [2, 0, 0, 4],
    [1, 5, 3, 1]
]
Enter fullscreen mode Exit fullscreen mode

Output

12
Enter fullscreen mode Exit fullscreen mode

Explanation

We take the following path: [0, 2, 1, 5, 3, 1]
Enter fullscreen mode Exit fullscreen mode

Example 3

Input

matrix = [
    [0, 2, 1],
    [2, 5, 0],
    [4, 1, 3]
]
Enter fullscreen mode Exit fullscreen mode

Output

11
Enter fullscreen mode Exit fullscreen mode

Explanation

We take the following path: [0, 2, 5, 1, 3]
Enter fullscreen mode Exit fullscreen mode

Intuition

we need to calculate the sum of coins in every cells, which equals max(up, left) + coins

Implementation

import java.util.*;

class Solution {
    public int solve(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int row = 1; row <= m; row++) {
            for (int col = 1; col <= n; col++) {
                dp[row][col] =
                    Math.max(dp[row - 1][col], dp[row][col - 1]) + matrix[row - 1][col - 1];
            }
        }
        return dp[m][n];
    }
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity

  • Time: O(m*n)
  • Space: O(m*n)

Top comments (0)

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.