I was asked by an interviewer from Microsoft (internship interview) to write code to determine the minimum steps/shortest path on a grid from some start to some goal, since this was very much related to my research in motion planning. I am providing the code here for the solution.
Now, the way Dynamic Programming works is that we break a big problem into smaller “sub-problems”. So we say that the cost-to-go from some location i,j is the cost to go to an adjacent element plus the cost to go from that adjacent element. We are of course assuming that at each time, one can only to an adjacent element (up, down, left, right, and diagonally). We set the cost to go to an adjacent element as 1, simply because that is the number of steps to reach an adjacent element. We then iterate over the costMatrix till the costMatrix converges to a constant value.
Steps:
1. Create a costMatrix where you set the cost to go for each cell as ‘1’ except the goal cell.
2. For the goal cell, set the cost to go as 0, since if you’re already at the goal cell, there is no expenditure to reach the goal!
3. While the costMatrix does not converge to a fixed value, iterate over all the elements and increment the cost-to-go from an element as 1 + minimum cost-to-go from an adjacent element.
Finally, you get a cost matrix with the cost to go from each cell stored in that cell. Now you can choose any cell as your starting cell and proceed by finding which adjacent node has the smallest cost-to-go and keep repeating this till you reach the goal.
Here is the C++ code