Maximum Amount of Money Robot Can Earn - Solution & Explanation

Problem Overview: You are given a grid where each cell represents money gained or lost when the robot enters it. The robot starts at the top-left and must reach the bottom-right moving only right or down. Some cells contain robbers (negative values). The robot can neutralize up to two robbers, preventing the loss. The goal is to compute the maximum amount of money the robot can collect along a valid path.

Approach 1: Brute Force DFS (Exponential Time)

Explore every possible path from (0,0) to (m-1,n-1) using depth‑first search. At each cell you decide whether to move right or down. If the value is negative and you still have robber neutralizations left, branch into two choices: take the loss or neutralize it. This generates up to three states per cell and quickly explodes in size. Time complexity is roughly O(2^(m+n)) in the worst case with O(m+n) recursion space, which is impractical for larger grids but useful to reason about the state transitions.

Approach 2: Memoized Search / Top-Down DP (O(m * n * 3))

The key observation is that many DFS states repeat. The robot's future earnings depend only on three values: the current row, the current column, and how many robber neutralizations remain. Cache results using a memo table dp[row][col][k], where k ranges from 0 to 2. From each state, recursively compute the best value from moving right or down. When the current cell contains a negative value and k > 0, you can either accept the loss or neutralize the robber and treat the cell value as zero. Store the maximum result in the memo table so the same state never recomputes.

This transforms the exponential search into a bounded dynamic programming problem. Each cell is evaluated for three possible neutralization states, producing O(m * n * 3) time complexity and the same O(m * n * 3) space complexity for memoization. The approach fits naturally with recursion and memo caching in languages like Python, Java, C++, Go, or TypeScript.

The solution models a classic grid path optimization problem from dynamic programming, extended with an extra decision dimension. Thinking of the grid as a state graph helps: each state branches to two neighbors while tracking remaining power-ups. This pattern appears in many matrix path problems and constrained optimization problems on arrays.

Recommended for interviews: Memoized DFS (top-down DP). Interviewers expect you to identify overlapping subproblems and introduce a state like (row, col, remainingNeutralizations). Explaining the brute-force recursion first demonstrates understanding of the path choices, then adding memoization shows strong dynamic programming instincts.