的不同上手路径一个机器人位于一个mxn的格子的左上角（下图中起点标记为“Start”）。机器人一次只能向下或向右移动一步。机器人尝试到达网格的右下角（下图中标记为“完成”）。总共有多少条不同的路径？示例1：输入：m=3,n=7输出：28示例2：输入：m=2,n=3输出：3解释：从左上角开始，共有3条路径路径可以到达右下角。Right->Right->DownRight->Down->RightDown->Right->Right示例3：输入：m=7，n=3输出：28示例4：输入：m=3，n=3输出：6Tips:1<=m,n<=100题目数据保证答案小于等于2*10^9深入思考这道题，乍一看最直观的思路就是用图论中的深度搜索，枚举有多少条路径。请注意，标题说机器人一次只能向下或向右移动一步。其实机器人走过的路径可以抽象成一棵二叉树，叶子节点就是终点！比如如图：此时不同的路径可以转化为求二叉树的叶子节点个数，代码如下：classSolution{private:intdfs(inti,intj,intm,intn){if(i>m||j>n)return0;//越界if(i==m&&j==n)return1;//找方法，相当于找叶子节点returndfs(i+1,j,m,n)+dfs(i,j+1,m,n);}public:intuniquePaths(intm,intn){returndfs(1,1,m,n);}};如果你提交代码，你会发现已经超时了！下面分析一下时间复杂度。这种深度搜索算法实际上遍历了整个二叉树。这棵树的深度其实是m+n-1（深度是从1开始计算的）。二叉树中的节点数为2^(m+n-1)-1。可以理解为深度搜索算法是遍历整棵满二叉树（其实并没有遍历整棵满二叉树，只是一种近似），所以上面的深度搜索代码的时间复杂度为，ascan可见，这是一个指数级的时间复杂度，非常大。动态规划机器人从(0,0)位置开始，到(m-1,n-1)结束。根据动态规则的五个部分来分析：确定dp数组（dp表）和下标dp[i][j]的含义：表示从(0,0)开始，到达(i,j)为dp[i][j]不同的路径。确定递推公式要求dp[i][j]，求导只有两个方向，即dp[i-1][j]和dp[i][j-1]。这个时候我们再回顾一下dp[i-1][j]是什么意思。从(0,0)的位置到(i-1,j)有几条路径。dp[i][j-1]也是如此。那么很自然地，dp[i][j]=dp[i-1][j]+dp[i][j-1]，因为dp[i][j]只从这两个方向过来。如何初始化dp数组初始化，首先dp[i][0]必须为1，因为从位置(0,0)到(i,0)只有一条路径，那么dp[0][j]也是一样的道理。所以初始化代码为：for(inti=0;i
