Frontend School

Robot Coin Collection

DSA
easy

Robot Coin Collection

Easy
Dynamic Programming
2D Grid
Matrix

Overview

Imagine a sophisticated robot deployed in a rectangular field, represented as a grid, where each cell contains a certain number of valuable coins. The robot's mission is to traverse this field, starting from the top-left corner and ending at the bottom-right corner, collecting as many coins as possible. The robot has a simple movement rule: it can only move one step right or one step down at a time. This problem models real-world scenarios in logistics, resource collection, and pathfinding where maximizing yield under constrained movement is crucial.

What you need to do / Task

Your task is to implement a function that determines the maximum total number of coins the robot can collect on its journey from the top-left (0, 0) to the bottom-right (m-1, n-1) cell of the grid.

Input & output

grid

  • Type: number[][]
  • Description: A 2D array of integers where grid[i][j] represents the number of coins available in the cell at row i and column j.

Return Value

  • Type: number
  • Description: The maximum total number of coins the robot can collect.

Clarifications

  • Movement: The robot can only move one step right (from (i, j) to (i, j+1)) or one step down (from (i, j) to (i+1, j)).
  • Collection: Coins at a cell are collected when the robot enters that cell. The starting cell's coins are collected, and the ending cell's coins are also collected.

Examples

1

Example 1

Input:

grid = [[1,3,1],[1,5,1],[4,2,1]]

Output:

12

Note:

The path (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) yields 1 + 3 + 5 + 2 + 1 = 12 coins, which is the maximum possible.

2

Example 2

Input:

grid = [[1,2],[3,4]]

Output:

8

Note:

Starting at (0,0) with 1 coin. To reach (1,1) (4 coins):

  • Path 1: (0,0) -> (0,1) -> (1,1) gives 1 + 2 + 4 = 7 coins.
  • Path 2: (0,0) -> (1,0) -> (1,1) gives 1 + 3 + 4 = 8 coins. The maximum is 8.
3

Example 3

Input:

grid = [[0]]

Output:

0

Note:

The robot starts and ends at the same cell (0,0), collecting 0 coins.

Constraints

Constraints & assumptions

  • 1 <= grid.length <= 200 (number of rows, m)
  • 1 <= grid[i].length <= 200 (number of columns, n). All rows will have the same length.
  • 0 <= grid[i][j] <= 100 (number of coins in any cell).
  • The grid will always be non-empty and contain at least one row and one column.

Out of scope

  • Diagonal movements are not allowed.
  • The grid will not contain any "obstacles" that block movement (all cells are traversable, though some might have 0 coins).

What interviewers evaluate

  • Dynamic Programming Application: Correct identification and implementation of a dynamic programming approach.
  • Base Case Handling: Accurate initialization and handling of edge conditions, particularly for the first row and column.
  • Optimal Solution: The solution should correctly compute the maximum coins within acceptable time and space complexity.
  • Code Quality: Clarity, readability, and maintainability of the implemented solution.

Loading editor...