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).

- I've set up the grid (
`coins`

), where the bottom-left cell is`(0,0)`

and the top-right is`(7,6)`

; i.e.,`coins[(1,2)] = 5`

. - I've also computed
`max_coins`

, the maximum number of coins Adam can collect along the way to a given cell, for the first column and row. - You need to
**fill in the logic in line 19**- the recursive step for`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?

×

Problem Loading...

Note Loading...

Set Loading...