#3418
Maximum Amount of Money Robot Can Earn
MediumArrayDynamic ProgrammingMatrixDynamic ProgrammingMatrix Traversal
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(m * n * k) |
| Space | O(1) | O(m * n * k) |
💡
Intuition
Time O(m * n * k)Space O(m * n * k)
Use dynamic programming to store the maximum coins collected at each cell, considering the number of robbers neutralized. This avoids recalculating results for already visited states.
⚙️
Algorithm
3 steps- 1Step 1: Initialize a 3D DP array where dp[i][j][k] represents the maximum coins at cell (i, j) with k robbers neutralized.
- 2Step 2: Fill the DP table by iterating through the grid and updating the maximum coins based on previous cells.
- 3Step 3: Return the maximum coins at the bottom-right corner considering both neutralized states.
solution.py12 lines
1def maxCoins(coins):
2 m, n = len(coins), len(coins[0])
3 dp = [[[-float('inf')] * 3 for _ in range(n)] for _ in range(m)]
4 dp[0][0][2] = coins[0][0]
5 for i in range(m):
6 for j in range(n):
7 for k in range(3):
8 if i > 0: dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k] + coins[i][j])
9 if j > 0: dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k] + coins[i][j])
10 if coins[i][j] < 0 and k > 0:
11 dp[i][j][k-1] = max(dp[i][j][k-1], dp[i][j][k] + abs(coins[i][j]))
12 return max(dp[m-1][n-1])ℹ
Complexity note: The complexity arises from filling a 3D DP table where m and n are the dimensions of the grid and k is the number of robbers neutralized.
- 1Dynamic programming is essential for optimizing overlapping subproblems.
- 2Tracking states (like neutralized robbers) can significantly enhance the solution.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.