#yyds干货盘点# 面试必刷TOP101:不同路径的数目(一)

1.简述:

描述

一个机器人在m×n大小的地图的左上角(起点)。

机器人每次可以向下或向右移动。机器人要到达地图的右下角(终点)。

可以有多少种不同的路径从起点走到终点?

#yyds干货盘点# 面试必刷TOP101:不同路径的数目(一)

备注:m和n小于等于100,并保证计算结果在int范围内

数据范围:#yyds干货盘点# 面试必刷TOP101:不同路径的数目(一),保证计算结果在32位整型范围内

要求:空间复杂度 #yyds干货盘点# 面试必刷TOP101:不同路径的数目(一),时间复杂度 #yyds干货盘点# 面试必刷TOP101:不同路径的数目(一)

进阶:空间复杂度 #yyds干货盘点# 面试必刷TOP101:不同路径的数目(一),时间复杂度 #yyds干货盘点# 面试必刷TOP101:不同路径的数目(一)

示例1

输入:

2,1

返回值:

1

示例2

输入:

2,2

返回值:

2

2.代码实现:

import java.util.*;
public class Solution {
public int uniquePaths (int m, int n) {
//dp[i][j]表示大小为i*j的矩阵的路径数量
int[][] dp = new int[m + 1][n + 1];
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
//只有1行的时候,只有一种路径
if(i == 1){
dp[i][j] = 1;
continue;
}
//只有1列的时候,只有一种路径
if(j == 1){
dp[i][j] = 1;
continue;
}
//路径数等于左方格子的路径数加上上方格子的路径数
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
}
发表评论

相关文章