Lintcode：不同的路径

问题：

有一个机器人的位于一个 m × n 个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

问有多少条不同的路径？

样例：

Example 1:

Input: n = 1, m = 3 Output: 1 Explanation: Only one path to target position.

Example 2:

Input: n = 3, m = 3 Output: 6 Explanation: D : Down R : Right 1) DDRR 2) DRDR 3) DRRD 4) RRDD 5) RDRD 6) RDDR

注意事项

n和m均不超过100

python：

class Solution: """ @param m: positive integer (1 <= m <= 100) @param n: positive integer (1 <= n <= 100) @return: An integer """ def uniquePaths(self, m, n): # write your code here if m == 1 or n == 1: return 1 nums = [[0 for i in range(n)] for j in range(m)] for i in range(m): nums[i][0] = 1 for j in range(n): nums[0][j] = 1 for i in range(1,m): for j in range(1,n): nums[i][j] = nums[i-1][j] + nums[i][j-1] return nums[m-1][n-1]

C++：

class Solution { public: /** * @param m: positive integer (1 <= m <= 100) * @param n: positive integer (1 <= n <= 100) * @return: An integer */ int uniquePaths(int m, int n) { // write your code here if(m == 1 || n == 1) { return 1; } vector<vector<int>> nums(m,vector<int>(n)); for(int i = 1; i < m; i++) { nums[i][0] = 1; } for(int j = 1; j < n; j++) { nums[0][j] = 1; } for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { nums[i][j] = nums[i-1][j] + nums[i][j-1]; } } return nums[m-1][n-1]; } };