题目描述:一个机器人位于一个 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
正常解法：本题是一道动态规划的题，第0行的第一个节点为1，第二个为第一个节点的值，第0列第一个节点为1，第二个·节点为上个节点的值，其余节点等于它的前面节点的值加它的后面节点的值。
图的广度优先搜索解法，构建一张图，每个节点指向它的右边一个节点和它的下边一个节点。使用一个数组来存储到当前节点有多上条路径，遍历所有节点得到所求结果。
代码实现:
class Solution {
public int uniquePaths(int m, int n) {//构造一个二维数组，借助此数组来构造图int[][] a = new int[m][n];for(int i=0;i<m;i++) {for(int j=0;j<n;j++) {a[i][j] = i*n+j;}}int[] sum = new int[m*n];//构造有向图Graph g = new Graph(m*n);for(int i=0;i<m;i++) {for(int j=0;j<n;j++) {if(i+1<m)g.addEdge(a[i][j], a[i+1][j]);if(j+1<n)g.addEdge(a[i][j], a[i][j+1]);}}//广度优先搜索使用队列来存储节点Queue<Integer> te = new PriorityQueue<>();//把起点加入队列中te.add(a[0][0]);到起点的路径数为1sum[0] =1;//广度优先搜索bfs(sum,g,te);//System.out.println(sum[m*n-1]);return sum[m*n-1];}public void bfs(int[] sum, Graph g,Queue<Integer> te) {while(!te.isEmpty()) {Integer v = te.remove();//从队列中取出节点并把它指向的节点w加入队列for(int w:g.adj(v)) {//到w的路径数等于它加上指向它的路径数sum[w] += sum[v];//如果w不在队列中，把w加入队列if(!te.contains(w))te.add(w);}}}//图结构class Graph{
Stack<Integer> [] adjs;public Graph(int v) {adjs = (Stack<Integer>[]) new Stack[v];for(int i=0;i<v;i++) {adjs[i] = new Stack<Integer>();}}public void addEdge(int v,int m) {adjs[v].push(m);}public Iterable<Integer> adj(int v){return adjs[v];}}
}