Unique Paths
Post
Cancel

# LeetCode #62: Unique Paths (C/C++).

medium

source: https://leetcode.com/problems/unique-paths/
C/C++ Solution to LeetCode problem 62. Unique Paths.

## Problem

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 * 109.

## Examples

### Example 1:

Input: m = 3, n = 7
Output: 28

### Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

## Constraints

• 1 <= m, n <= 100

## Solution

This can be solved using dynamic programing (either recursive or iterative).

• We can use a map to memoize the results, but that makes it slower, so, we will allocate a vector of vectors (representing the board).
• The iterative version is a shorter solution.

### Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { vector<vector<int>> dp; private: int paths(int m, int n, int r, int c) { if (r+1 == m && c+1 == n) return 1; if (r == m || c == n) return 0; if (dp[r][c] != 0) return dp[r][c]; dp[r][c] = 0; dp[r][c] += paths(m, n, r + 1, c); dp[r][c] += paths(m, n, r, c + 1); return dp[r][c]; } public: int uniquePaths(int m, int n) { dp = vector(m, vector<int>(n, 0)); int r = paths(m, n, 0, 0); return r; } }; 

### Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public: int uniquePaths(int m, int n) { dp = vector(m, vector<int>(n, 1)); for (int r=1; r<m; r++) { for (int c=1 ; c<n; c++) dp[r][c] = dp[r][c-1] + dp[r-1][c]; } return dp[m-1][n-1]; } };