Unique Paths

• Lintcode : 114 / Leetcode : 62
• Level : Easy

Problem

A robot is located at the top-left corner of a m x n 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?

Example
Example 1:

Input: n = 1, m = 3
Output: 1    
Explanation: Only one path to target position.
Example 2:

Input:  n = 3, m = 3
Output: 6    
Explanation:
    D : Down
    R : Right
    1) DDRR
    2) DRDR
    3) DRRD
    4) RRDD
    5) RDRD
    6) RDDR
Notice
m and n will be at most 100.
The answer is guaranteed to be in the range of 32-bit integers

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(m n)
space: O(m n)

Answer

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

tags: DP

​