刷题记录 动态规划-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. 不同路径
题目:62. 不同路径 难度:中等 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” &#x…...
docker直接运行arm下的docker
运行环境是树莓派A 处理器是 arm32v6 安装了docker,运行lamp 编译安装php的时候发现要按天来算,于是用电脑vm下的Ubuntu系统运行arm的docker 然后打包到a直接导入运行就可以了 第一种方法 sudo apt install qemu-user-static 导入直接运行就可以了…...
014-STM32单片机实现矩阵薄膜键盘设计
1.功能说明 本设计主要是利用STM32驱动矩阵薄膜键盘,当按下按键后OLED显示屏上会对应显示当前的按键键值,可以将此设计扩展做成电子秤、超市收银机、计算器等需要多个按键操作的单片机应用。 2.硬件接线 模块管脚STM32单片机管脚矩阵键盘行1PA0矩阵键盘…...
Sentinel 断路器在Spring Cloud使用
文章目录 Sentinel 介绍同类对比微服务雪崩问题问题原因问题解决方案请求限流线程隔离失败处理服务熔断解决雪崩问题的常见方案有哪些? Sentineldocker 安装账号/ 密码项目导入簇点链路请求限流线程隔离Fallback服务掉线时的处理流程 服务熔断 Sentinel 介绍 随着微…...
[内网安全] 内网渗透 - 学习手册
这是一篇专栏的目录文档,方便读者系统性的学习,笔者后续会持续更新文档内容。 如果没有特殊情况的话,大概是一天两篇的速度。(实验多或者节假日,可能会放缓) 笔者也是一边学习一边记录笔记,如果…...
算法总结-二分查找
文章目录 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有点状况,导致apikey一直生成不了,用kimi练练手。这是一个基于 Moonshot AI 的 Kimi 接口开发的聊天应用程序,使用 Python Tkinter 构建图形界面。 项目结构 项目由三个主要Python文件组成: 1. main_kimi.py…...
动手学深度学习-3.2 线性回归的从0开始
以下是代码的逐段解析及其实际作用: 1. 环境设置与库导入 %matplotlib inline import random import torch from d2l import torch as d2l作用: %matplotlib inline:在 Jupyter Notebook 中内嵌显示 matplotlib 图形。random:生成…...
Spring 面试题【每日20道】【其二】
1、Spring MVC 具体的工作原理? 中等 Spring MVC 是 Spring 框架的一部分,专门用于构建基于Java的Web应用程序。它采用模型-视图-控制器(MVC)架构模式,有助于分离应用程序的不同方面,如输入逻辑、业务逻辑…...
嵌入式八股文面试题(一)C语言部分
1. 变量/函数的声明和定义的区别? (1)变量 定义不仅告知编译器变量的类型和名字,还会分配内存空间。 int x 10; // 定义并初始化x int x; //同样是定义 声明只是告诉编译器变量的名字和类型,但并不为它分配内存空间…...
Vue06
目录 一、声明式导航-导航链接 1.需求 2.解决方案 3.通过router-link自带的两个样式进行高亮 二、声明式导航的两个类名 1.router-link-active 2.router-link-exact-active 三、声明式导航-自定义类名(了解) 1.问题 2.解决方案 3.代码演示 四…...
deepseek-r1模型本地win10部署
转载自大佬:高效快速教你deepseek如何进行本地部署并且可视化对话 deepseek 如果安装遇到这个问题 Error: Post “http://127.0.0.1:11434/api/show”: read tcp 127. 用管理员cmd打开 接着再去切换盘符d: cd 文件夹 重新下载模型:ollama run deepseek…...
自定义数据集 使用scikit-learn中SVM的包实现SVM分类
生成自定义数据集 生成一个简单的二维数据集,包含两类数据点,分别用不同的标签表示。 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 方法用于将宽格式(wide format)的 DataFrame 转换为长格式(long format)的 DataFrame。这种转换在数据处理和可视化中非常有用,尤其是在处理多列数据时。 宽格式 vs 长格式 宽格式(Wide F…...
一文讲解Spring中应用的设计模式
我们都知道Spring 框架中用了蛮多设计模式的: 工厂模式呢,就是用来创建对象的,把对象的创建和使用分开,这样代码更灵活。代理模式呢,是用一个代理对象来控制对真实对象的访问,可以在访问前后做一些处理。单…...
Linux的基本指令(下)
1.find指令 Linux下find命令在⽬录结构中搜索⽂件,并执⾏指定的操作。 Linux下find命令提供了相当多的查找条件,功能很强⼤。由于find具有强⼤的功能,所以它的选项也很多,其中⼤部分选项都值得我们花时间来了解⼀下。 即使系统中含…...
HAO的Graham学习笔记
前置知识:凸包 摘录oiwiki 在平面上能包含所有给定点的最小凸多边形叫做凸包。 其定义为:对于给定集合 X,所有包含 X 的凸集的交集 S 被称为 X 的 凸包。 说人话就是用一个橡皮筋包含住所有给定点的形态 如图: 正题:…...
Elasticsearch Queries
Elasticsearch Compound Queries Elasticsearch 的 Compound Queries 是一种强大的工具,用于组合多个查询子句,以实现更复杂的搜索逻辑。这些查询子句可以是叶查询(Leaf Queries)或复合查询(Compound Queries…...
利用matlab寻找矩阵中最大值及其位置
目录 一、问题描述1.1 max函数用法1.2 MATLAB中 : : :的作用1.3 ind2sub函数用法 二、实现方法2.1 方法一:max和find2.2 方法二:max和ind2sub2.3 方法对比 三、参考文献 一、问题描述 matlab中求最大值可使用函数max,对于一维向量࿰…...
SQL入门到精通 理论+实战 -- 在 MySQL 中学习SQL语言
目录 一、环境准备 1、MySQL 8.0 和 Navicat 下载安装 2、准备好的表和数据文件: 二、SQL语言简述 1、数据库基础概念 2、什么是SQL 3、SQL的分类 4、SQL通用语法 三、DDL(Data Definition Language):数据定义语言 1、操…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析
1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器(TI)推出的一款 汽车级同步降压转换器(DC-DC开关稳压器),属于高性能电源管理芯片。核心特性包括: 输入电压范围:2.95V–6V,输…...
