/ Data Structure and Algorithms  

Leetcode 62. Unique Paths

Question



Count the number of paths from top-left corner to bottom-right corner. Can only move down or right.

Similar Questions

Solution

Use the idea of dynamic programming, we can define a 2D array. Each element of the array represent the unique path starting from this point to bottom-right point. For example, dp[i][j] = 5 means that starting from (i, j), there are 5 unique paths.

Let’s observe the problem. The first insight we can have is that the point on the last row and last column can only have 1 unique path (because we can only move right and down).

For other points, the number of unique paths is the sum of unique path of the point below it and right to it. Thus we have our dynamic programming formula: dp[i][j] = dp[i + 1][j] + dp[i][j + 1]. And we start to fill the dp array from second last row.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// dp array
int[][] result = new int[n][m];

result[n - 1][m - 1] = 1;
// fill last row with 1
for (int i = 0; i < m - 1; i++) {
    result[n - 1][i] = 1;
}

// fill right most column with 1
for (int i = 0; i < n - 1; i++) {
    result[i][m - 1] = 1;
}

// fill the table from second last row
for (int i = n - 2; i >= 0; i--) {
    for (int j = m - 2; j >= 0; j--) {
        result[i][j] = result[i][j + 1] + result[i + 1][j];
    }
}

return result[0][0];

Time complexity O(n * m), space complexity O(n * m).