题解 | #求路径#

方法一：递归 机器人走到（m，n）的路径数=走到（m-1，n）的路径数+走到（m，n-1）的路径数；因此可以用递归求解

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        if(m==1||n==1) return 1;
        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }
};

方法（二）还是递归的思路，以空间换时间

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        vector<vector<int>> graph(m,vector<int> (n,1));
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                graph[i][j]=graph[i-1][j]+graph[i][j-1];
            }
        }
        return graph[m-1][n-1];
    }
};

方法三：按照方法二是思路，继续压缩空间

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        vector<int> graph(n,1);
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                graph[j]=graph[j]+graph[j-1];
            }
        }
        return graph[n-1];
    }
};