Skip to content

62. Unique Paths

Description

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.

 

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

Solutions

Solution 1: Dynamic Programming

Thinking

The first idea is to search: only right or down, enumerate every path. With \(m, n \le 100\), the path count is combinatorial, so a raw search explodes.

The bottleneck is revisiting the same cell. Paths into \((i, j)\) come only from above or the left and do not overlap, so the subproblems add.

Store that count in \(f[i][j]\) and fill in row-major order so the dependencies already exist. Start at \(1\); the bottom-right cell is the answer.

We define \(f[i][j]\) to represent the number of paths from the top left corner to \((i, j)\), initially \(f[0][0] = 1\), and the answer is \(f[m - 1][n - 1]\).

Consider \(f[i][j]\):

  • If \(i > 0\), then \(f[i][j]\) can be reached by taking one step from \(f[i - 1][j]\), so \(f[i][j] = f[i][j] + f[i - 1][j]\);
  • If \(j > 0\), then \(f[i][j]\) can be reached by taking one step from \(f[i][j - 1]\), so \(f[i][j] = f[i][j] + f[i][j - 1]\).

Therefore, we have the following state transition equation:

\[ f[i][j] = \begin{cases} 1 & i = 0, j = 0 \\ f[i - 1][j] + f[i][j - 1] & \textit{otherwise} \end{cases} \]

The final answer is \(f[m - 1][n - 1]\).

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the number of rows and columns of the grid, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [[0] * n for _ in range(m)]
        f[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i:
                    f[i][j] += f[i - 1][j]
                if j:
                    f[i][j] += f[i][j - 1]
        return f[-1][-1]

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func uniquePaths(m int, n int) int {
    f := make([][]int, m)
    for i := range f {
        f[i] = make([]int, n)
    }
    f[0][0] = 1
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i > 0 {
                f[i][j] += f[i-1][j]
            }
            if j > 0 {
                f[i][j] += f[i][j-1]
            }
        }
    }
    return f[m-1][n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function uniquePaths(m: number, n: number): number {
    const f: number[][] = Array(m)
        .fill(0)
        .map(() => Array(n).fill(0));
    f[0][0] = 1;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (i > 0) {
                f[i][j] += f[i - 1][j];
            }
            if (j > 0) {
                f[i][j] += f[i][j - 1];
            }
        }
    }
    return f[m - 1][n - 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let (m, n) = (m as usize, n as usize);
        let mut f = vec![1; n];
        for i in 1..m {
            for j in 1..n {
                f[j] += f[j - 1];
            }
        }
        f[n - 1]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
    const f = Array(m)
        .fill(0)
        .map(() => Array(n).fill(0));
    f[0][0] = 1;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (i > 0) {
                f[i][j] += f[i - 1][j];
            }
            if (j > 0) {
                f[i][j] += f[i][j - 1];
            }
        }
    }
    return f[m - 1][n - 1];
};

Solution 2: Dynamic Programming (Prefilled Borders)

Thinking

Solution 1 tests “has an above / has a left” on every cell, so the border keeps taking extra branches.

The first row can arrive only from the left, the first column only from above, and both are all \(1\). Prefill those borders and the interior adds unconditionally. Same complexity, cleaner code.

Fill the first row and first column with \(1\), then only compute interior cells \(f[i][j] = f[i-1][j] + f[i][j-1]\). Time and space stay \(O(m \times n)\).

1
2
3
4
5
6
7
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                f[i][j] = f[i - 1][j] + f[i][j - 1]
        return f[-1][-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int uniquePaths(int m, int n) {
        var f = new int[m][n];
        for (var g : f) {
            Arrays.fill(g, 1);
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func uniquePaths(m int, n int) int {
    f := make([][]int, m)
    for i := range f {
        f[i] = make([]int, n)
        for j := range f[i] {
            f[i][j] = 1
        }
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            f[i][j] = f[i-1][j] + f[i][j-1]
        }
    }
    return f[m-1][n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function uniquePaths(m: number, n: number): number {
    const f: number[][] = Array(m)
        .fill(0)
        .map(() => Array(n).fill(1));
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
    const f = Array(m)
        .fill(0)
        .map(() => Array(n).fill(1));
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
};

Solution 3: Dynamic Programming (Rolling Array)

Thinking

The first two solutions keep a full \(m \times n\) table. \(f[i][j]\) only needs the previous row \(f[i-1][j]\) and the left cell \(f[i][j-1]\), so the first dimension can go.

After compressing to 1D, \(f[j]\) is still the previous row until we update it; add \(f[j-1]\) to get the current row. Space drops to \(O(n)\), time stays the same.

\(f[i][j]\) depends only on the previous row and the left cell, so a 1D array of length \(n\) is enough. The time complexity is \(O(m \times n)\) and the space complexity is \(O(n)\).

1
2
3
4
5
6
7
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                f[j] += f[j - 1]
        return f[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int uniquePaths(int m, int n) {
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[j] += f[j - 1];
            }
        }
        return f[n - 1];
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func uniquePaths(m int, n int) int {
    f := make([]int, n+1)
    for i := range f {
        f[i] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            f[j] += f[j-1]
        }
    }
    return f[n-1]
}

1
2
3
4
5
6
7
8
9
function uniquePaths(m: number, n: number): number {
    const f: number[] = Array(n).fill(1);
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            f[j] += f[j - 1];
        }
    }
    return f[n - 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
    const f = Array(n).fill(1);
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            f[j] += f[j - 1];
        }
    }
    return f[n - 1];
};

Comments