You are given an m x n grid. A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). The robot can move either right or down at any point in time.
The grid contains a value coins[i][j] in each cell:
coins[i][j] >= 0, the robot gains that many coins.coins[i][j] < 0, the robot encounters a robber, and the robber steals the absolute value of coins[i][j] coins.The robot has a special ability to neutralize robbers in at most 2 cells on its path, preventing them from stealing coins in those cells.
Note: The robot's total coins can be negative.
Return the maximum profit the robot can gain on the route.
Example 1:
Input: coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
Output: 8
Explanation:
An optimal path for maximum coins is:
(0, 0) with 0 coins (total coins = 0).(0, 1), gaining 1 coin (total coins = 0 + 1 = 1).(1, 1), where there's a robber stealing 2 coins. The robot uses one neutralization here, avoiding the robbery (total coins = 1).(1, 2), gaining 3 coins (total coins = 1 + 3 = 4).(2, 2), gaining 4 coins (total coins = 4 + 4 = 8).Example 2:
Input: coins = [[10,10,10],[10,10,10]]
Output: 40
Explanation:
An optimal path for maximum coins is:
(0, 0) with 10 coins (total coins = 10).(0, 1), gaining 10 coins (total coins = 10 + 10 = 20).(0, 2), gaining another 10 coins (total coins = 20 + 10 = 30).(1, 2), gaining the final 10 coins (total coins = 30 + 10 = 40).Constraints:
m == coins.lengthn == coins[i].length1 <= m, n <= 500-1000 <= coins[i][j] <= 1000When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
Every room offers two choices, and both are explored from scratch. Taking the room adds its money and restarts the decision two rooms ahead, while skipping it restarts at the next room. The larger result is kept, and the first decision begins at the opening room.
Here's how the algorithm would work step-by-step:
def max_money_brute_force(rooms):
def find_max_from_index(current_index):
# Base case: if we've gone past the last room, no more money can be collected.
if current_index >= len(rooms):
return 0
# Explore the first choice: collect money from the current room and skip the next.
money_if_taken = rooms[current_index] + find_max_from_index(current_index + 2)
# Explore the second choice: skip the current room and decide on the next one.
money_if_skipped = find_max_from_index(current_index + 1)
# The optimal choice for this subproblem is the maximum of the two branching paths.
return max(money_if_taken, money_if_skipped)
# The process starts from the very first room (index 0) to find the overall maximum.
return find_max_from_index(0)The fast version solves the street from the last room backward, keeping only two running totals. One total is the best money available starting at the next room, and the other is the best money available starting two rooms ahead. Each room chooses the larger of taking its money plus the farther total, or keeping the nearer total, and those two totals then slide one room backward.
Here's how the algorithm would work step-by-step:
def max_money_robot_can_earn(money_in_each_room):
number_of_rooms = len(money_in_each_room)
if number_of_rooms == 0:
return 0
if number_of_rooms == 1:
return money_in_each_room[0]
# This tracks the max money earnable from the next room onwards.
max_money_from_next_room = money_in_each_room[number_of_rooms - 1]
# This tracks the max money earnable from two rooms ahead onwards.
max_money_from_two_rooms_ahead = 0
# Iterate backwards from the second-to-last room to solve for each subproblem.
for current_room_index in range(number_of_rooms - 2, -1, -1):
# For each room, decide whether to rob it or skip it based on maximum future earnings.
current_max_earnings = max(
money_in_each_room[current_room_index] + max_money_from_two_rooms_ahead,
max_money_from_next_room
)
max_money_from_two_rooms_ahead = max_money_from_next_room
max_money_from_next_room = current_max_earnings
return max_money_from_next_room| Case | How to Handle |
|---|---|
| The street has no rooms | There is nothing to collect, so the result is zero. |
| The street has a single room | That room is taken, because it has no neighbor that could set off the alarm. |
| The street has exactly two rooms | Only the larger amount is taken, because the two rooms are adjacent. |
| Every room holds zero | Every choice totals zero, so the result is zero. |
| A rich room sits between poor rooms | The rich room is taken and both of its neighbors are left behind. |
| Large and small amounts alternate | Each room keeps the better of taking it plus the best total from two rooms ahead, or skipping ahead by one room. |