This time, some cells contain obstacles that the robot cannot enter. Count the paths from the top left to the bottom right, still moving only right or down.
DSA Animator › DSA Revision › Dynamic Programming › Unique Paths II
Remember: an obstacle simply forces the count to 0. In the rolling array, dp of c already holds the value from above. The video solves Unique Paths II (LeetCode 63, Medium) with the 2D Grid DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Unique Paths II animation.
This time, some cells contain obstacles that the robot cannot enter. Count the paths from the top left to the bottom right, still moving only right or down.
In a 3 by 3 grid with an obstacle in the centre, there are 2 paths. One goes along the top and down the right side, and the other goes down the left and along the bottom.
Exploring every path and checking for obstacles repeats the same work many times. The same recurrence as before still works.
Use the same rule: paths into a cell equal paths from above plus paths from the left. But an obstacle cell gets 0, because no path can pass through it. This also handles obstacles in the first row or column: everything after them becomes 0. If the start itself is an obstacle, the answer is 0.
The start has 1 path. The first row becomes 1, 1, 1. In row 1, the first cell is 1, and the obstacle is 0. The last cell of row 1 is 0 plus 1, which is 1. In row 2, the cells become 1, then 1 plus 0, which is 1, then 1 plus 1, which is 2. So there are 2 paths.
In code, use a one dimensional array of the row width, with dp of 0 set to 1 when the start is free. For each cell, if it is an obstacle, set dp of c to 0. Otherwise, if c is more than 0, add dp of c minus 1, which is the value on the left. Return the last value, so it's O of m times n time and O of n space.
Remember: an obstacle simply forces the count to 0. In the rolling array, dp of c already holds the value from above.