ProblemA robot is located at the top-left corner of a NXN grid. 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. How many possible unique paths are there?
UniquePaths(row, column) = 0 if row > N or column > N
1 if row ==N and column == N
UniquePaths(row+1, column) + UniquePaths(row, column+1)
i.e, the recursive method has optimal substructure and overlapping sub problems. So, the problem can be solved using Dynamic Programming.
DP - Memoization (Top-Down - Lazy)
DP - Bottom-Up
Finding the number of paths mathematically
Say, if the grid is 4X4 => i.e, the number of unique paths is nothing but all possible permutations of RRRDDD where R represents right and D represents Down. For details, please see the attached image: