题目描述

机器人位于一个 m x n 网格的左上角, 在下图中标记为“Start” (开始)。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，在下图中标记为“Finish”(结束)。

问有多少条不同的路径？

注意: m 和 n 的值均不超过 100。

我的解法——DP（AC）

每个格子可能从上面、左面走下来：dp[i]/[j] = dp[i - 1]/[j] + dp[i]/[j - 1]
复杂度O(n2)
结果：Beat67.24%

class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[-1 for j in range(n)] for i in range(m)]
        
        for i in range(m):
            dp[i][0] = 1
        for j in range(1,n):
            dp[0][j] = 1
            
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                
        return dp[m - 1][n - 1]

次优解法——DP

使用一维数组B[x]记录一行行内每个坐标数据，并对每行循环更新，大大减少空间复杂度。
对于起点到点(i,j)的路径总数：ways[j]= 起点到点(i-1, j) 的路径总数：ways[j] + 起点到点(i, j-1)的路径总数ways[j-1]，于是我们就得到递推式：ways[j] = ways[j] + ways[j-1]
空间复杂度从原来的 O(n*m)下降为 O(n)

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

最优解法——组合数学

根据题目可知，从起点到终点的总步数是一定的，右行或下行的次数也是一定的。我们只需要确定在总部数中哪些步数右行或是哪些步数下行即可知道其对应的路径。这里运用到排列组合的思想。
C(m+n-2,m-1)或C(m+n-2,n-1)
总时间O(1)，空间O(1)

public class Solution {
    public int uniquePaths(int m, int n) {
        double res = 1;
        for (int i = 1; i <= n - 1; i++) 
            res *= ((double) (m + i - 1) / (double) i);
        return (int) Math.round(res);
    }
}