一、问题描述
一个机器人位于一个 m x n **网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
题目链接：机器人走迷宫
二、题目要求
考察
动态规划中等题型 建议用时5~15min
数据要求
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
样例
m=3，n=7 输出28 m=3，n=2 输出3 m=3，n=3 输出6
三、问题分析
还是用我们的三步走老套路：
第一步含义搞懂：
这是二维数组，要求出不同路径，那么就用二维数组 dp[i][j]存储不同的路径个数。
第二步变量初始：
dp[1][1]=1 原地踏步不就是吗？ 一步步写太多了，不想写了，我放一个编译结果图片，偷懒一下。
第三步规律归纳：
看看上面的图片有什么特别的地方，有时间可以自己动手写一下，印象会更加深刻，当时我就写了一遍。
是不是当前数组位置的到数 = 左面的数字 + 上面的数字啊！
所以dp[m][n]=dp[m][n-1]+dp[m-1][n];
三步走，打完收工！
四、编码实现
usingnamespacestd; intuniquePaths(intm, intn) { inti,j,dp[102][102]={0};//初始化变量for(i=1;i<=m;i++)//循环判断 { for(j=1;j<=n;j++) { if(i==1&&j==1) { dp[1][1]=1;//初始化变量 } elsedp[i][j]=dp[i][j-1]+dp[i-1][j];//规律归纳 } } // for(i=0;i<=m;i++)//输出当前数组元素的值// {// for(j=0;j<=n;j++)// {// cout<<dp[i][j]<<" ";// }cout<<"\n";// }returndp[m][n];//返回结果} intmain() { intm,n; cin>>m>>n;//输入数组大小cout<<uniquePaths(m, n) ;//赋值给动态规划功能的函数return0; }
五、测试结果
输入3 7：
