Dynamic-Programming

Problem

Starting from the top-left corner, what is the number of possible unique paths to reach the bottom-right corner, if you can only move either down or right at any point in time, and the path cannot include any square that is an obstacle?

Solution

The addition of obstacles has these implications:

• I can’t use the combinatorics formula because the problem is no longer easy to define in general terms.
• The logic in the inner loop of the DP solution needs to take the obstacles into account.

#dynamic-programming