Maximum Rocks Collection

Moderate
0/80
0 upvote
Asked in company
Goldman Sachs

Problem statement

You are an explorer on an expedition to collect rare rocks. You are given a 2D grid of size m x n, where each cell grid[i][j] represents a city containing a certain number of these rocks.


Your journey must start at the bottom-left corner (grid[m-1][0]) and end at the top-right corner (grid[0][n-1]). From any city (i, j), you are only allowed to move to the city directly up (i-1, j) or to the city directly right (i, j+1). You cannot move outside the grid boundaries.


The total number of rocks you collect is the sum of the rocks in every city you visit, including the starting and ending cities. Your task is to find a path that maximizes the total number of rocks collected.


Return the maximum number of rocks you can collect.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains two space-separated integers, m and n, representing the number of rows and columns in the grid.

The next m lines each contain n space-separated integers, representing the grid.


Output Format: 
Print a single integer representing the maximum number of rocks that can be collected.


Note: 
A simple greedy approach (always moving to the adjacent city with more rocks) may not yield the optimal overall path. This problem has optimal substructure and overlapping subproblems, making it a great candidate for dynamic programming.
Sample Input 1:
3 3
1 2 3
4 8 2
1 5 3


Sample Output 1:
19


Explanation for Sample 1:
The optimal path is (2,0) -> (2,1) -> (1,1) -> (1,2) -> (0,2).
The total number of rocks collected is 1 + 5 + 8 + 2 + 3 = 19.


Sample Input 2:
3 3
1 1 100
1 10 1
20 1 1


Sample Output 2:
123


Explanation for Sample 2:
The optimal path is (2,0) -> (2,1) -> (2,2) -> (1,2) -> (0,2).
The total number of rocks collected is 20 + 1 + 1 + 1 + 100 = 123. A greedy path starting with (2,0) -> (1,0) (value 1) instead of (2,0) -> (2,1) (value 1) would lead to a suboptimal total.


Expected Time Complexity:
The expected time complexity is O(m*n).


Constraints:
1 <= m, n <= 200
0 <= grid[i][j] <= 1000

Time Limit: 1 sec
Approaches (1)
Dynamic Programming
Time Complexity
Space Complexity
Code Solution
(100% EXP penalty)
Maximum Rocks Collection
Full screen
Console