Unique Paths Problem


Description

LeetCode Problem 62.

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?

Example 1:

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

Example 2:

1
2
3
4
5
6
7
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

Example 3:

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

Example 4:

1
2
Input: m = 3, n = 3
Output: 6

Constraints:

  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 10^9.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if ((i == 1) || (j == 1))
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};




Related Posts

Maximum Product Subarray Problem

LeetCode 152. Given an integer array nums, find a contiguous...

House Robber Problem

LeetCode 198. You are a professional robber planning to rob...

Dungeon Game Problem

LeetCode 174. The demons had captured the princess and imprisoned...

Best Time To Buy And Sell Stock IV Problem

LeetCode 188. You are given an integer array prices where...

Palindrome Partitioning II Problem

LeetCode 132. Given a string s, partition s such that...

Triangle Problem

LeetCode 120. Given a triangle array, return the minimum path...