首页 > 其他分享 >#yyds干货盘点# 面试必刷TOP101:不同路径的数目(一)

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

时间:2022-09-29 17:11:50浏览次数:56  
标签:yyds 机器人 示例 int 复杂度 路径 必刷 TOP101 dp

1.简述:

描述

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

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

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

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

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

数据范围:,保证计算结果在32位整型范围内

要求:空间复杂度 ,时间复杂度 

进阶:空间复杂度 ,时间复杂度 

示例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];
}
}

标签:yyds,机器人,示例,int,复杂度,路径,必刷,TOP101,dp
From: https://blog.51cto.com/u_15488507/5723517

相关文章

  • #yyds干货盘点# 面试必刷TOP101:矩阵的最小路径和
    1.简述:描述给定一个 n*m 的矩阵 a,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,输出所有的路径中最小的路径和。数据范......
  • #yyds干货盘点# 前端歌谣的刷题之路-第九十七题-symbol
    前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了从......
  • yydsqwqw
    向量的旋转一共有三种表示方法:旋转矩阵、欧拉角和四元数,接下来我们介绍一下每种旋转方法的原理以及相互转换方式。旋转矩阵坐标变换的作用在一个机器人系统中,每个测量元......
  • yyds
    向量的旋转一共有三种表示方法:旋转矩阵、欧拉角和四元数,接下来我们介绍一下每种旋转方法的原理以及相互转换方式。旋转矩阵坐标变换的作用在一个机器人系统中,每个测量元......
  • 盘点 10个 C# 开源项目 yyds!
    盘点10个C#开源项目yyds!搜罗Github挖掘优质开源项目,分享高效率工具!​关注 6人赞同了该文章只推荐干货!当然这些开源项目都是个人或组织......