Treasure Grid
Hard · rating 1850 · Dynamic Programming, Matrix
Starting at the top-left of a grid, collect as much treasure as possible reaching the bottom-right, moving only right, down, or diagonally down-right. The first line has r and c. The next r lines each have c integers (cell values, possibly negative). Print the maximum total collected (start and end cells included).
Constraints: 1 ≤ r, c ≤ 500
Editorial
Approach
Each cell is reachable from above, from the left, or diagonally from the upper-left, so the best total ending at a cell is its own value plus the best of those three predecessors. Fill the grid once; the bottom-right holds the answer.
dp[0][0] = g[0][0]
for each cell (i, j) != (0,0):
best = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) # whichever exist
dp[i][j] = best + g[i][j]Complexity
Time: O(r·c). Space: O(r·c).
Related problems
- Maximal Square — Hard
- Minimum Path Sum — Hard
- Balanced Bracket Count — Hard
- Equal Subset Partition — Hard
- Word Break — Hard
- 0/1 Knapsack — Hard