求路径-题解

题目描述
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

示例1
输入
复制
2,1
返回值
复制
1
示例2
输入
复制
2,2
返回值
复制
2

解决方案：
动态规划，三行代码。
建立坐标系为起点(1, 1)，终点(m, n)。
到达m，n的路径是到达(m-1, n)的路径之和加上到达(m, n-1)的路径之和，当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);
    }
};