leetcode  62. 不同路径  medium          

题目描述：

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

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

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

 

解题思路：

跟leetcode 64 类似的题  https://blog.csdn.net/speargod/article/details/98257115

下面的代码用了按行滚的，空间压缩技巧。

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m<=0 || n<=0)
            return 0;
        // 按行滚，所以是列的长度。
        vector<int> dp(n,1);
        for(int i=1;i<m;++i)
            for(int j=1;j<n;++j)
                dp[j]=dp[j]+dp[j-1];
        
        return dp[n-1];
        
    }
};