Leetcode 62. Unique Paths [medium][java]

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

Solution 1: dynamic programming

Consideration

1. We use a 2d array to store # of ways from start point to current point.
2. For a point(i, j), ways[i,j] = ways[i-1][j] +ways[i][j-1].

Time complexity: O(mn), space complexity: O(mn)

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] res = new int[m][n];
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0) {
                    res[i][j] = 1;
                } else {
                    res[i][j] = res[i-1][j] + res[i][j-1];
                }
            }
        
        return res[m-1][n-1];
    }
}
           

Solution 2: an improved version of solution 1

Consideration

1. For a point(i, j), ways[i,j] = ways[i-1][j] +ways[i][j-1]. That is, ways[j] = ways[j] + ways[j-1].

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

class Solution {
    public int uniquePaths(int m, int n) {
        int[] ways = new int[n];
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
                if(j == 0) {
                    ways[j] = 1;
                } else {
                    ways[j] = ways[j] + ways[j-1];
                }
            }
        
        return ways[n-1];
    }
}
           

Solution 3: use recursion, but will have time limitation problem

Consideration

1. Use recursion, the intermediate result is not reserved. Each time we should recalculate the results, so it is more time consuming than dynamic programming.

class Solution {
    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        return uniquePaths(m-1,n)+uniquePaths(m, n-1);
    }
}
           

References

1. https://blog.csdn.net/happyaaaaaaaaaaa/article/details/50856112