题目地址：https://leetcode-cn.com/problems/unique-paths/
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记
为“Finish”）。
问总共有多少条不同的路径？
image.png
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
编程思路
此题用到两个技巧：
-
动态规划
为什么使用动态规划？因为从左上角（起点）到达每一个地点的不同路径数目，都可以通过与其邻接的地点的路径数目累加获得。如下图，计算右下角地点的路径数目可以通过其前序地点的路径数相加而来。
image.png -
图的广度优先遍历
机器人行走的路径点，可以抽象成有向图，从起点节点出发，进行广度优先遍历，即可从起点到终点逐个完成路径数目的的计算。为什么用广度优先而不用深度优先？因为深度优先会出现某靠后节点所需的前序节点尚未计算的情况，而广度优先不会。3x2情况可以抽象成如下的图(Graph)，来一次广度优先遍历，最后一个节点遍历完成后便得到了答案。（画中数值的含义是从起点到该节点的不同路径的数量）
image.png
代码
#include <iostream>
#include <queue>
using namespace std;
class Solution {
public:
int uniquePaths(int m, int n) {//m :width,n :height
//two queues for BFS
queue<int> x;
queue<int> y;
//two var for queue operation
int tmpX;
int tmpY;
int **pathAmount;//store his known path amount
bool **nodePushed;//store visit state
pathAmount=new int*[n];
nodePushed=new bool*[n];
for(int tmp=0;tmp<n;tmp++){
pathAmount[tmp]=new int[m];
nodePushed[tmp]=new bool[m];
for(int inner=0;inner<m;inner++){
pathAmount[tmp][inner]=0;
nodePushed[tmp][inner]=false;
}
}
pathAmount[0][0]=1;
//start position in
x.push(0);
y.push(0);
nodePushed[0][0]=true;
//BFS
while(x.size()>0){
//queue head out
tmpX=x.front();
x.pop();
tmpY=y.front();
y.pop();
if((tmpX+1)<m){//non m boader
pathAmount[tmpY][tmpX+1]+=pathAmount[tmpY][tmpX];//update path amount of the next
if(!nodePushed[tmpY][tmpX+1]){//push into queue if not visited
x.push(tmpX+1);
y.push(tmpY);
nodePushed[tmpY][tmpX+1]=true;
}
}
if((tmpY+1)<n){//non n boader
pathAmount[tmpY+1][tmpX]+=pathAmount[tmpY][tmpX];//update path amount of the next
if(!nodePushed[tmpY+1][tmpX]){//push into queue if not visited
x.push(tmpX);
y.push(tmpY+1);
nodePushed[tmpY+1][tmpX]=true;
}
}
}
return pathAmount[n-1][m-1];
}
};
int main(){
Solution solution;
printf("res:%d",solution.uniquePaths(21,21));
}
性能：
image.png
