Unique Paths

Unique Paths

 

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?

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

Note: m and n will be at most 100.


Naive Way: 第一反应是用DP做。
基本逻辑为：
opt(i,j) // # of paths from (0,0) to (i,j)
// base case
opt(i,0)=1 0<=i<m
opt(0,j)=1 0<=j<n
// iteration
opt(i,j) = opt(i-1,j) + opt(i,j-1)


算法复杂度为O(nm), space O(mn)

public class Solution {
    public int uniquePaths(int m, int n) {
        int opt[][] = new int[m][n];
        // base case
        for(int i = 0;i < m;i++) opt[i][0] = 1;
        for(int j = 0;j < n;j++) opt[0][j] = 1;
        // ieration
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                opt[i][j] = opt[i-1][j] + opt[i][j-1];
        return opt[m-1][n-1];
    }
}


将2D矩阵用两个1D数组表示可节省空间。space O(m+n)

public class Solution {
    public int uniquePaths(int m, int n) {
        int row[] = new int[m];
        int col[] = new int[n];
        // base case
        for(int i = 0;i < m;i++) row[i] = 1;
        for(int j = 0;j < n;j++) col[j] = 1;
        // ieration
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                row[i] += col[j];
                col[j] = row[i];
            }
        }
        return row[m-1];
    }
}


Improved Way: Discuss里有两种更好的方法，一种是对两个1D数组的再做简化。
因为从上一格到下一格只有一条路，下一格其实并不需要额外记录，只需用上一格的数据就可以，所以一旦上一层的前一格记录好了，当前层的前一个也就记录好了，因为二者是一样的。只需要对每一层做row[i] = row[i] + row[i-1]的操作了。

space 是 O(min(m,n))

public class Solution {
    public int uniquePaths(int m, int n) {
        if(m > n) return uniquePaths(n,m);
        int row[] = new int[m];
        // base case
        for(int i = 0;i < m;i++) row[i] = 1;
        // ieration
        for(int j = 1;j < n;j++)
            for(int i = 1;i < m;i++)
                row[i] += row[i-1];
        return row[m-1];
    }
}


还有一个方法是 这个问题和杨辉三角 是一样的，可以构建一格杨辉三角取对应位置的值。这里等我做了杨辉三角再补充。