Unique Paths II
Medium · Dynamic Programming · about 15 minutes
Asked at Bloomberg, Amazon, Microsoft, Google, D. E. Shaw.
A robot starts at the top-left of an m × n grid and moves only right or down to the bottom-right. Some cells have obstacles (1); free cells are 0. Return the number of unique paths that avoid every obstacle.