# A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
# The robot can only move either down or right at any point in time.
# The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
# How many possible unique paths are there?
The problem state thats the robot may only move from down or to the right to get to the bottom-right corner, this makes things easier.
For an example, I have a 2x2 matrix the only way I can get from top-left corner to bottom-right corner is 2. Which is the total number of ways I can get to 0,1 and 1,0, the top and left of 2,2 (the destination). Hence we can derive the equation A[i][j] = A[j-1][i] + A[j][i-1], to represent the total number of ways to get to a location in the matrix.
We can solve this problme using depth-frist search, go through all possible path from the end to the start. But the draw back is that with dfs the time complexity will be O(N^4) which will time out on large matrix.
To solve that we can use dynamic programming instead, to approach the problem from start head to the end. The idea is to make an identical size matrix filled with 1s, and ignore the edges start traversal from 1,1 since there will be only 1 way to get through the edge spots. Similarly, filled out the possible ways of getting into each spot in that matrix by the formula above (left + top combination). In the end, the bottom-right spot should contain the total number of ways to get to that spot from the beginning.
# Follow up for "Unique Paths":
The idea is similar to the previous problem, but added the ability to have obstacles.
We can use dynamic programming as well, filling out an all 1s array as we go. But we need to beware to escape the obstacles. To do that we initialize the matrix with all zeros, fill out the edge spots with 1s except for where obstacles are.
Then we may start the traversal similar to last problem, but escape all spots with 1s in the original matrix since they are obstacles.