想更方便阅读代码的朋友可以点这里。
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
问题分析：
这是一个寻找路径条数的问题，而且存在一个限制条件：机器人只能向右走或者向下走，这样的话就意味着如镜中不存在向左走再向右走这样无解的情况。除此我们对图进行分析可以知道，当机器人走到了与终点同一行或者同一列的位置时，就只有一条路径方案了，敏锐的人可能发现了，这个可以做为递归的终止条件，那么我们如何确定递归的划分呢？递归的划分其实在题目中已经告诉了我们方法。题目高告诉我们机器人只能向下或者向右，这是不是就意味着两条递归路径呢。
举个实例，就假设当前机器人在坐标(1,5)处，终点在(2,6)处，这样的话，我们可以发现机器人向右走得时候只有一条路径，向下走得时候也只有一条路径，那么从点(1,5)到(2,6）就有turnRinght+turnDown=2种路径了，在向上一层，例如(1,4)到（2，6）向下只有一条路径，向右走一步就到了(1,5)由之前的结果我们就可以知道有两条路径，这样的话，(1,4)到（2，6）有3条路径。
代码如下：
class Solution {
private int[][] cache; //缓存 备忘录模式
public int uniquePaths(int column, int row) {
if(column==0||row==0){
return 0;
}
cache=new int[row][column];
return recursion(column,row,0,0);
}
public int recursion(int column,int row,int x,int y){
if(column-1==y||row-1==x){
return 1;
}
if(cache[x][y]!=0){
return cache[x][y];
}
int right= recursion(column,row,x+1,y);
int down= recursion(column,row,x,y+1);
cache[x][y]=right+down;
return right+down;
}
}
因为单纯的使用递归会使得的时间和空间消耗过大，不满足题意，所以在代码中使用了备忘录模式，添加了一个缓存用来存储已经走过的点到终点的路径数量。
网友评论