In the grid above, the number of gold coins in each cell is given. Adam needs to start in the bottom-left square and move to the top-right square, moving only up and to the right.
What is the maximum number of gold coins he can collect?
This can be solved using a recursive approach (dynamic programming).
coins
), where the bottom-left cell is (0,0)
and the top-right is (7,6)
; i.e., coins[(1,2)] = 5
.max_coins
, the maximum number of coins Adam can collect along the way to a given cell, for the first column and row. max_coins
for the rest of the cells - and run the code! Hint: What are the possible states just before you reach a given cell?
Bonuses: How can you initialize max_coins
differently to avoid the separate cases for the first column and row, and just have a single recursive loop? Also, can you modify the code to return the actual path that gives the maximum gold?