[Algorithm] Leetcode #62 Unique Paths(DP/Medium/C++)

Problem Link: https://leetcode.com/problems/unique-paths/

This question can be solved using Dynamic Programming. Notice that it can move only in the right or left direction. Let’s first think of a topdown approach.

Let dp[i][j] = Number of ways to reach to the destination (i,j) from (0,0) on the grid. Then, we have a base case dp[0][0]=1 since there’s only one way to reach (0,0) from (0,0) by not moving. The recurrence relation would be

dp[i][j] = dp[i-1][j] + dp[i][j-1] since we can always come from up or left. However, we must consider the boundary conditions. When i<0 or j<0, it’s out of the boundary of the grid, so there’s no way to reach to the position out of the grid.

Top down Approach

Time Complexity: O(n*m)

Bottom up Approach

Time Complexity: O(n*m)