This is fairly similar to the previous problem “Leetcode 62: Unique Paths” but here we will set the memo cell value to zero if there is an obstacle in that cell, as there is no route to the finish from that cell. There is a weird leetcode test case that causes integer overflow if int is used in the memo vector. Changing the DP memo to use long instead of int resolves the problem.
Here is the source code for my various solutions:
Recursive with DP memo
Iterative DP, O(n²) time and space
Iterative DP with O(n) space optimisation