Path with Maximum Gold
Medium · Backtracking · about 20 minutes
Asked at Google, Amazon, Meta, Microsoft, Bloomberg.
In an m × n gold mine, each cell holds some gold (0 means empty). Start at any cell with gold and move up, down, left or right, collecting gold; you can't visit a cell twice or step on a 0-cell. Return the maximum gold you can collect. At most 25 cells contain gold.