apache网站部署,济宁最新通知今天,建设工程造价管理基础知识,公司做网站需要准备什么软件题目
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish” #xff09;。
问总共有多少条不同的路径#xff1f; …题目
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径 输入m 3, n 7 输出28 示例 2
输入m 3, n 2 输出3 解释 从左上角开始总共有 3 条路径可以到达右下角。
向右 - 向下 - 向下向下 - 向下 - 向右向下 - 向右 - 向下 示例 3
输入m 7, n 3 输出28 示例 4
输入m 3, n 3 输出6
提示
1 m, n 100 题目数据保证答案小于等于 2 * 109
代码编写
这道题目难道还算可以我们假设i,j且i和j的区间分别是[0,m)和[0,n)。则有f(i,j)表示向右边移动了i次和向下移动了j次因为条件只能向右和向下所以f(i,j) f(i-1,j) f(i,j-1)。由题意得f(i,0)和f(0,j)都是1,所以进行计算就可以了。 class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint ans(m,vectorint(n));for(int i 0;i m;i){ans[i][0] 1;}for(int j 0;jn;j){ans[0][j] 1;}for(int i 1;i m;i){for(int j 1;j n;j){ans[i][j] ans[i-1][j] ans[i][j-1];}}return ans[m-1][n-1];}
};
