题目描述:
A robot is located at the top-left corner of a m x n grid (marked ‘Start‘ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish‘ in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
解题思路:
组合数学中的例子
1 class Solution { 2 public: 3 int uniquePaths(int m, int n) { 4 // 递归超时 5 // if (n == 1 || m == 1) { 6 // return 1; 7 // } else { 8 // return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); 9 // } 10 11 // DP 12 vector<vector<int>> matrix(m, vector<int>(n, 1)); 13 for (int i = 1; i< m; ++i) { 14 for (int j = 1; j < n; ++j) { 15 matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]; 16 } 17 } 18 19 return matrix[m - 1][n - 1]; 20 } 21 };
原文：http://www.cnblogs.com/skycore/p/5292373.html