刷题-leetcode：62. 不同路径

题目地址：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 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
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