I am trying to solve a programming puzzle that goes as follows: Imagine we have a market or mall with several stores in it. The market is represented as an NxN grid where 1 <= N <= 20 and every cell in the grid is a store. Say we have an initial amount of money M to spend where 1 <= M <= 200. Starting from the upper left corner of the grid (0,0), we can only move right or down. Every cell contains an number 1 <= P <= 10 that represents the amount of money we spend by traversing that cell.
The goal is to find the path where we are left with the least amount of money when we get to the bottom right cell (N,N) without exceeding the amount M that we start wih. If we cannot find such a path we return -1. Note that we don't pay anything at the start (0,0) but we pay everywhere else including the final step (N,N).
Now I figure that for an NxN grid, the number of moves needed to get from the upper left to bottom right corner regardless of what path we choose is going to be 2N-2. My approach so far is to write a recursive function that at every step looks at the two choices we face, either go right or down (or in case we start from the end and work our way back, look left or up) and pick the best choice and subtract it from out current total amount of money.
I am not able to figure out the criteria to decide which choice to make at each step. Your help would be greatly appreciated.
