网站文章在哪发布做seo,微信小程序制作价格,网站建设类岗位有哪些,学网页设计的怎么赚钱一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish” #xff09;。
问总共有多少条不同的路径#xff1f;
思路一…一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
思路一动态规划
int uniquePaths(int m, int n){int dp[m][n];int i,j0;for(i0;im;i){for(j0;jn;j){if(i0||j0){dp[i][j]1;}else{dp[i][j]dp[i-1][j]dp[i][j-1];}}}return dp[m-1][n-1];
}
时间复杂度O(mn)空间复杂度O(mn)
分析
本题要求从左上角到右下角共有多少条不同路径可利用动态规划到每个格子的不同路径等于到左边前一个路径数加上边前一个路径数最后返回dp[m-1][n-1]
思路二组合排列
int Combinations(int up, int down){long prod 1;int left down - up 1, right 1;while(right up){prod * left;prod / right;left;right;}return prod;
}int uniquePaths(int m, int n){int para (m - 1 n - 1) ? m - 1 : n - 1;return Combinations(para, m n - 2);
}
时间复杂度O(n)空间复杂度O(1)
分析
本题同时可直接用排列组合进行计算因为机器人需要向下走n-1步向右走m-1步即共走mn-2步中间有n-1步向下走计算即可得到答案。
比较
两个思路比较组合排列的方式可直接计算结果避免构造数组在内存方面占优且组合排列计算的时间复杂度为O(n)优于第一种不断向后递推的思路运行速度更快。
总结
本题考察动态规划的应用每个格子考虑左边前一个和上边前一个的值或直接使用组合排列的方法得到答案。
