题目描述
一个机器人位于一个 m x n 网格的左上角 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
问总共有多少条不同的路径？
分析
问题等价于在笛卡尔坐标系下，从（m,n）到（1,1）进行移动操作，其中移动操作只为左移一格或下移一格。
-
从（m,n）到（1,1）的移动：在（m,n）处只能移动到（m-1,n）或（m,n-1）;
设
表示从(m,n)移动到(1,1)所有的路径数目，其中
。
解题思路: 递归
算法
func ( m , n ) :
if m == 1 or m == 1 :
return 1
left = f( m-1, n )
down = f( m, n-1 )
return left+down
不需要特殊数据结构
代码
class Solution{
public :
int uniquePaths( int m, int n ){
if ( m == 1 || n == 1 ){
return 1 ;
}
int left = uniquePaths( m-1, n );
int down = uniquePaths( m, n-1 ) ;
return left + down
}
};
问题在于这样的递归解法中，计算量成指数增长，需要量级的计算。经典例子如：计算斐波那契数列的第n个值
使用动态规划（DP,自底向上）可以避免重复计算。
解题思路：动态规划
算法
arr:
二维数组，arr[i-1,j-1]存储从（i,j）到（1,1）的路径总数
初始化：
arr[0][:] = 1
arr[:][0] = 1
迭代计算：
for i = 1 to m :
for j = 1 to n :
arr[i][j] = arr[i-1][j] + arr[i][j-1]
return arr[m-1][n-1]
数据结构
使用可随机访问的顺序表：vector
代码
class Solution {
public:
int uniquePaths(int m, int n) {
// 存储结构初始化
vector<vector<int>> arr ;
for ( int i = 0 ; i < m ; ++ i ){
vector<int> tmp(n) ;
arr.push_back( tmp ) ;
}
for ( int i = 0 ; i < m ; ++ i ){
arr[i][0] = 1 ;
}
for ( int j = 0 ; j < n ; ++ j ){
arr[0][j] = 1 ;
}
// dp迭代过程
for ( int i = 1 ; i < m ; ++ i ){
for ( int j = 1 ; j < n ; ++ j ){
arr[i][j] = arr[i-1][j] + arr[i][j-1] ;
}
}
return arr[m-1][n-1] ;
}
};
相关问题与感想
记得刚接触编程的时候遇到的一个问题，在做这道题的时候突然想起来，和这道题是一样的，分享给大家。
有m个1和n个0，请问有多少中不同的组合方式？
对于任意组合方式，考虑两种情况：最后一个字符是0，最后一个字符是1
两道题目不能说是十分相似，简直是一模一样。可以将向下移动看作是1，向左移动看作是0.
PS.
相比较于其他已有的leetcode刷题笔记，我希望能够提供相关的解题分析和部分相关问题的链接，使得大家能获得一个较好的分析与相关问题的比较。
偶尔会进行类似题目的总结工作，有需要的读者可以对这份工作进行关注。
如果你发现有相关的错误或者表述不当不清晰的地方，请进行评论，我会尽快进行核对勘正。
