题目：
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是深度优先搜索，超时。代码2是建立了备忘录数组的深度优先搜索，顺利通过！代码1：
class Solution {
public:
int uniquePaths(int m, int n) {
if(m<1||n<1)return 0;
if(m==1&&n==1)return 1;
if(m==1||n==1){
return 1;
}else{
return uniquePaths(m-1,n)+uniquePaths(m,n-1);
}
}
};class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> A(n+1,INT_MAX);
vector<vector<int>> B(m+1,A);
return uniquePaths(m,n,B);
}
private:
int uniquePaths(int m, int n, vector<vector<int>> &B){
if(m<1||n<1)return 0;
if(m==1&&n==1)return 1;
if(m==1||n==1){
B[m][n]=1;
return 1;
}else{
int m_1=B[m-1][n]==INT_MAX?uniquePaths(m-1,n,B):B[m-1][n];
int n_1=B[m][n-1]==INT_MAX?uniquePaths(m,n-1,B):B[m][n-1];
B[m][n]=m_1+n_1;
return B[m][n];
}
}
};给一个动态规划的解法：
class Solution {
public:
int uniquePaths(int m, int n) {
if(m<1||n<1)return 0;
if(m==1||n==1)return 1;
int f[m][n];
for(int i=0;i<m;i++)f[i][0]=1;
for(int i=0;i<n;i++)f[0][i]=1;
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
f[i][j]=f[i-1][j]+f[i][j-1];
}
}
return f[m-1][n-1];
}
};【Leetcode】Unique Paths,布布扣,bubuko.com
原文：http://blog.csdn.net/ussam/article/details/22187967