Home August | 2022 | Leetcoding Challenge
Post
Cancel

August | 2022 | Leetcoding Challenge

01 July | 62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., $grid[0][0]$). The robot tries to move to the bottom-right corner (i.e., $grid[m - 1][n - 1]$). The robot can only move either down or right at any point in time.

Given the two integers $m$ and $n$, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to $2 * 10^9$.

Combinatorics

1
2
3
4
5
6
7
8
9
10
11
12
13
int uniquePaths(int m, int n) {

    int N = n+m-2;
    int r = min(n,m) - 1;

    double res = 1;

    for(int i=1; i<=r; ++i, N--)
        res = res * (N) / i;


    return (int)res;
    }

2D Memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    int solve(int i,int j,int m,int n,vector<vector<int>> &dp)
    {
        if(i>=m||j>=n)
            return 0;

        if(i==m-1&&j==n-1)
            return 1;
            
        if(dp[i][j]!=-1)
            return dp[i][j];
        
        return dp[i][j]=solve(i+1,j,m,n,dp)+solve(i,j+1,m,n,dp);
    }
    
    int uniquePaths(int m, int n) {
      vector<vector<int>> dp(m,vector<int>(n,-1));
        return solve(0,0,m,n,dp);
    }

1D Memoization

1
2
3
4
5
6
7
8
9
    int uniquePaths(int m, int n) {
        vector<int> cur(n, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] += cur[j - 1];
            }
        }
        return cur[n - 1];
    }

Tabulation

1
2
3
4
5
6
7
8
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for (int i = 1; i < m; i++) 
            for (int j = 1; j < n; j++) 
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            
        return dp[m - 1][n - 1];
    }

02 July |

###

1

03 July |

###

1

04 July |

###

1

05 July |

###

1

06 July |

###

1

07 July |

###

1

08 July |

###

1

09 July |

###

1

10 July |

###

1

11 July |

###

1

12 July |

###

1

13 July |

###

1

14 July |

###

1

15 July |

###

1

16 July |

###

1

17 July |

###

1

18 July |

###

1

19 July |

###

1

20 July |

###

1

21 July |

###

1

22 July |

###

1

23 July |

###

1

24 July |

###

1

25 July |

###

1

26 July |

###

1

27 July |

###

1

28 July |

###

1

29 July |

###

1

30 July |

###

1
This post is licensed under CC BY 4.0 by the author.

August | 2022 | POTD GFG

Day 1 Array | Striver 180 | takeUforward