LeetCode题解：不同路径

题目描述

一个机器人位于一个m × n网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图到达网格的右下角。
问总共有多少条不同的路径？

示例

image.png

输入：m = 3, n = 7
输出：28

方法思路

我们使用一个二维数组dp[][]记录从起始点到当前该结点的所有路径。
除了左边和上边空格外，其他空格都有两个来源（左边与上边）。
所以，这是个很明显的动态规划题。状态变化方程为：dp[i][j]=dp[i-1][j]+dp[i][j-1]。
网格左边与上边的网格点比较特殊，其只有一个来源（比如左边网格来源只能使上方），我们将其初始化为1。

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

复杂度分析

• 时间复杂度：O(mn)。
• 空间复杂度：O(mn)，即为存储所有状态需要的空间。注意到f(i，j)仅与第i行和第i-1行的状态有关，因此我们可以使用滚动数组替代代码中的二位数组，使空间复杂度降低为O(n)。