62 Unique Paths

https://leetcode.com/problems/unique-paths/#/description

A robot is located at the top-left corner of amxngrid (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?

分析及代码

时间复杂度没法变，但是空间复杂度可以压成一维

public int uniquePaths(int m, int n) {
    int[] path = new int[n];
    Arrays.fill(path, 1);
    for(int i = 1; i < m; i++) {
        int sameRowLastCol = 1;
        for(int j = 1; j < n; j++) {
            path[j] += path[j - 1];
        }
    }
    return path[n - 1];
}

O(mn)