62.不同路径

2020-05-15

# 题目

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

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

问总共有多少条不同的路径？

示例 1:
1
2
3
4
5
6
7
8
9
10
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下

向右 -> 向下 -> 向右

向下 -> 向右 -> 向右
示例 2:
1
2
输入: m = 7, n = 3
输出: 28
提示：

1 <= m, n <= 100

题目数据保证答案小于等于 2 * 10 ^ 9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

总共有多少条路径？是很明显的动态规划问题，很简单：暴力法解决时一定会出现重复计算路径的情况，因此最直观的优化就是动态规划。

使用动态规划需要数组记录起点到目标位置的路径数，我们自下而上进行考虑，用 $P(m,n)$ 表示路径数：

$P(1,1)=1$
$P(1,2)=1$
$P(2,1)=1$
$P(2,2)=2$

我们似乎需要一个 $m*n$ 的二维数组，然而仔细思考可以发现，由于每次只能向下或向右，也就意味着我们到达一个新位置，上一个位置只能是上面一格或左面一格，所以我们可以按行或按列计算逐行/列自上而下/自左而右计算。

状态转移表达式：

$P(m,n)=P(m-1,n)+P(m,n-1)$

边界情况：第一行所有值都为1

特殊情况： $m=1$ 或 $n=1$

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m==1 || n==1) return 1;
        vector<int> row_last(n, 1);
        vector<int> row_curr(n);
        for(int r=1; r<m; ++r){          
            for(int c=0; c<n; ++c){
                if(c) row_curr[c] = row_curr[c-1];
                else row_curr[c] = 0;
                row_curr[c] += row_last[c];
                row_last[c] = row_curr[c];
            }
        }       
        return row_curr[n-1];
    }
};

时间复杂度 $O(MN)$
空间复杂度 $O(N)$