## DEV Community 👩‍💻👨‍💻 is a community of 963,274 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Wenqi Jiang

Posted on

# 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]
]
``````

### Output

``````9
``````

### Explanation

``````We take the following path: [0, 3, 1, 1, 4]
``````

## Example 2

### Input

``````matrix = [
[0, 3, 1, 1],
[2, 0, 0, 4],
[1, 5, 3, 1]
]
``````

### Output

``````12
``````

### Explanation

``````We take the following path: [0, 2, 1, 5, 3, 1]
``````

## Example 3

### Input

``````matrix = [
[0, 2, 1],
[2, 5, 0],
[4, 1, 3]
]
``````

### Output

``````11
``````

### Explanation

``````We take the following path: [0, 2, 5, 1, 3]
``````

# 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];
}
}
``````

## Time Complexity

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