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

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)