当前位置: 首页 > news >正文

刷题记录 动态规划-6: 62. 不同路径

题目:62. 不同路径

难度:中等

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:

输入:m = 3, n = 7
输出:28

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

一、模式识别

本题我一共找到了三种解法:

首先最容易想到的就是基于递归的DFS(深度优先搜索),

然后如果沿着递推公式能想到从终点返回起点这一层就能写出动态规划解法

最后代码随想录还给出了算组合数的方法(数论),我数学没那么好,想不到

1.DFS

该方法顺着题干很容易想到,而且该方法就是动态规划方法的递推公式

2.动态规划

本题属于经典动态规划问题,而且动规的很多要素题干中已经直接给出

五部曲:

1.动规数组意义:位于位置(i, j)时剩余的总步数

2.递推公式:dp(i, j) = dp(i - 1, j) + dp(i, j - 1)

解释:

机器人处于位置(i, j)时,每次只能向下或者向右移动一步两种选择,

分别可以到达(i - 1, j)和位置(i, j - 1),

3.初始化:题干:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )

4.遍历顺序:本题常规,根据递推公式:

行遍历套列遍历或列遍历套行遍历均可,但注意是从终点反向到起点

5.举例:当机器人走到边缘位置(m == 1 or n == 1),路径便只剩下一条

3.数论:算组合数

无论怎么走,从起点(m, n)到终点(1, 1)都要走m + n - 2步,

其中,横向m - 1步,纵向n - 1步

因此该问题就顺理成章的转化成了C(m + n - 2), (m - 1)的组合问题

二、代码实现

1.DFS

这方法很好想,而且代码简介可读性强,但就是有个小小的问题:会超时!

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 or n == 1:return 1return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

问题源于其指数级的时间复杂度:O(2^(m + n - 1) - 1)

2.动态规划

(1)二维OMN空间写法

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 or n == 1:return 1dp = [[1] * n for _ in range(m)]for i in range(m):for j in range(n):if i != 0 and j != 0:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m - 1][n - 1]
  • 时间复杂度:O(m × n)
  • 空间复杂度:O(m × n)

耗时:0ms

(2)一维ON空间写法

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 or n == 1:return 1dp = [1] * nfor i in range(m):for j in range(n):if i != 0 and j != 0:dp[j] += dp[j - 1]return dp[n - 1]
  • 时间复杂度:O(m × n)
  • 空间复杂度:O(n)

耗时:3ms

可读性有点差,所以稍微解释一下,和二维空间代码的对应关系:

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 和 dp[j] += dp[j - 1]

dp[i][j]: 更新后的dp[j]

dp[i - 1][j]: 更新前的dp[j]

dp[i][j - 1]: dp[j - 1]

3.数论:算组合数

class Solution:def uniquePaths(self, m: int, n: int) -> int:num = 1a, b = m + n - 2, min(m - 1, n - 1)count = bwhile count > 0:num *= aa -= 1while b > 0 and num % b == 0:num //= bb -= 1count -= 1return num
  • 时间复杂度:O(m)
  • 空间复杂度:O(1)

耗时:0ms

相关文章:

刷题记录 动态规划-6: 62. 不同路径

题目&#xff1a;62. 不同路径 难度&#xff1a;中等 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#x…...

docker直接运行arm下的docker

运行环境是树莓派A 处理器是 arm32v6 安装了docker&#xff0c;运行lamp 编译安装php的时候发现要按天来算&#xff0c;于是用电脑vm下的Ubuntu系统运行arm的docker 然后打包到a直接导入运行就可以了 第一种方法 sudo apt install qemu-user-static 导入直接运行就可以了…...

014-STM32单片机实现矩阵薄膜键盘设计

1.功能说明 本设计主要是利用STM32驱动矩阵薄膜键盘&#xff0c;当按下按键后OLED显示屏上会对应显示当前的按键键值&#xff0c;可以将此设计扩展做成电子秤、超市收银机、计算器等需要多个按键操作的单片机应用。 2.硬件接线 模块管脚STM32单片机管脚矩阵键盘行1PA0矩阵键盘…...

Sentinel 断路器在Spring Cloud使用

文章目录 Sentinel 介绍同类对比微服务雪崩问题问题原因问题解决方案请求限流线程隔离失败处理服务熔断解决雪崩问题的常见方案有哪些&#xff1f; Sentineldocker 安装账号/ 密码项目导入簇点链路请求限流线程隔离Fallback服务掉线时的处理流程 服务熔断 Sentinel 介绍 随着微…...

[内网安全] 内网渗透 - 学习手册

这是一篇专栏的目录文档&#xff0c;方便读者系统性的学习&#xff0c;笔者后续会持续更新文档内容。 如果没有特殊情况的话&#xff0c;大概是一天两篇的速度。&#xff08;实验多或者节假日&#xff0c;可能会放缓&#xff09; 笔者也是一边学习一边记录笔记&#xff0c;如果…...

算法总结-二分查找

文章目录 1.搜索插入位置1.答案2.思路 2.搜索二维矩阵1.答案2.思路 3.寻找峰值1.答案2.思路 4.搜索旋转排序数组1.答案2.思路 5.在排序数组中查找元素的第一个和最后一个位置1.答案2.思路 6.寻找旋转排序数组中的最小值1.答案2.思路 1.搜索插入位置 1.答案 package com.sunxi…...

基于python的Kimi AI 聊天应用

因为这几天deepseek有点状况&#xff0c;导致apikey一直生成不了&#xff0c;用kimi练练手。这是一个基于 Moonshot AI 的 Kimi 接口开发的聊天应用程序&#xff0c;使用 Python Tkinter 构建图形界面。 项目结构 项目由三个主要Python文件组成&#xff1a; 1. main_kimi.py…...

动手学深度学习-3.2 线性回归的从0开始

以下是代码的逐段解析及其实际作用&#xff1a; 1. 环境设置与库导入 %matplotlib inline import random import torch from d2l import torch as d2l作用&#xff1a; %matplotlib inline&#xff1a;在 Jupyter Notebook 中内嵌显示 matplotlib 图形。random&#xff1a;生成…...

Spring 面试题【每日20道】【其二】

1、Spring MVC 具体的工作原理&#xff1f; 中等 Spring MVC 是 Spring 框架的一部分&#xff0c;专门用于构建基于Java的Web应用程序。它采用模型-视图-控制器&#xff08;MVC&#xff09;架构模式&#xff0c;有助于分离应用程序的不同方面&#xff0c;如输入逻辑、业务逻辑…...

嵌入式八股文面试题(一)C语言部分

1. 变量/函数的声明和定义的区别&#xff1f; &#xff08;1&#xff09;变量 定义不仅告知编译器变量的类型和名字&#xff0c;还会分配内存空间。 int x 10; // 定义并初始化x int x; //同样是定义 声明只是告诉编译器变量的名字和类型&#xff0c;但并不为它分配内存空间…...

Vue06

目录 一、声明式导航-导航链接 1.需求 2.解决方案 3.通过router-link自带的两个样式进行高亮 二、声明式导航的两个类名 1.router-link-active 2.router-link-exact-active 三、声明式导航-自定义类名&#xff08;了解&#xff09; 1.问题 2.解决方案 3.代码演示 四…...

deepseek-r1模型本地win10部署

转载自大佬&#xff1a;高效快速教你deepseek如何进行本地部署并且可视化对话 deepseek 如果安装遇到这个问题 Error: Post “http://127.0.0.1:11434/api/show”: read tcp 127. 用管理员cmd打开 接着再去切换盘符d: cd 文件夹 重新下载模型&#xff1a;ollama run deepseek…...

自定义数据集 使用scikit-learn中SVM的包实现SVM分类

生成自定义数据集 生成一个简单的二维数据集&#xff0c;包含两类数据点&#xff0c;分别用不同的标签表示。 import numpy as np import matplotlib.pyplot as plt# 生成数据 np.random.seed(42) X np.r_[np.random.randn(100, 2) - [2, 2], np.random.randn(100, 2) [2, …...

pandas的melt方法使用

Pandas 的 melt 方法用于将宽格式&#xff08;wide format&#xff09;的 DataFrame 转换为长格式&#xff08;long format&#xff09;的 DataFrame。这种转换在数据处理和可视化中非常有用&#xff0c;尤其是在处理多列数据时。 宽格式 vs 长格式 宽格式&#xff08;Wide F…...

一文讲解Spring中应用的设计模式

我们都知道Spring 框架中用了蛮多设计模式的&#xff1a; 工厂模式呢&#xff0c;就是用来创建对象的&#xff0c;把对象的创建和使用分开&#xff0c;这样代码更灵活。代理模式呢&#xff0c;是用一个代理对象来控制对真实对象的访问&#xff0c;可以在访问前后做一些处理。单…...

Linux的基本指令(下)

1.find指令 Linux下find命令在⽬录结构中搜索⽂件&#xff0c;并执⾏指定的操作。 Linux下find命令提供了相当多的查找条件&#xff0c;功能很强⼤。由于find具有强⼤的功能&#xff0c;所以它的选项也很多&#xff0c;其中⼤部分选项都值得我们花时间来了解⼀下。 即使系统中含…...

HAO的Graham学习笔记

前置知识&#xff1a;凸包 摘录oiwiki 在平面上能包含所有给定点的最小凸多边形叫做凸包。 其定义为&#xff1a;对于给定集合 X&#xff0c;所有包含 X 的凸集的交集 S 被称为 X 的 凸包。 说人话就是用一个橡皮筋包含住所有给定点的形态 如图&#xff1a; 正题&#xff1a…...

Elasticsearch Queries

Elasticsearch Compound Queries Elasticsearch 的 Compound Queries 是一种强大的工具&#xff0c;用于组合多个查询子句&#xff0c;以实现更复杂的搜索逻辑。这些查询子句可以是叶查询&#xff08;Leaf Queries&#xff09;或复合查询&#xff08;Compound Queries&#xf…...

利用matlab寻找矩阵中最大值及其位置

目录 一、问题描述1.1 max函数用法1.2 MATLAB中 : : :的作用1.3 ind2sub函数用法 二、实现方法2.1 方法一&#xff1a;max和find2.2 方法二&#xff1a;max和ind2sub2.3 方法对比 三、参考文献 一、问题描述 matlab中求最大值可使用函数max&#xff0c;对于一维向量&#xff0…...

SQL入门到精通 理论+实战 -- 在 MySQL 中学习SQL语言

目录 一、环境准备 1、MySQL 8.0 和 Navicat 下载安装 2、准备好的表和数据文件&#xff1a; 二、SQL语言简述 1、数据库基础概念 2、什么是SQL 3、SQL的分类 4、SQL通用语法 三、DDL&#xff08;Data Definition Language&#xff09;&#xff1a;数据定义语言 1、操…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...