首页 > itarticle > 62.unique paths

62.unique paths

admin 11月 12, 2020 0

Dynamic Programming, Medium

Question

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?

img
Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

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

Answer

1
2
3
4
5
6
7
8
9
10
11
 
class  {
    public int uniquePaths(int m, int n) {
        int[][] res = new int[m+1][n+1];
        res[1][1] = 1;
        for(int i = 1;i <= m; i++)
            for(int j = 1; j <= n; j++)
                if(i > 1 || j > 1)
                    res[i][j] = res[i-1][j] + res[i][j-1];
        return res[m][n];
    }
}

Time complexity: O(m*n)

Space complexity: O(m*n)

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

Time complexity: O(m*n)

Space complexity: O(n)

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能