代码随想录算法训练营第三十三天 | 62.不同路径 63.不同路径

LeetCode 62.不同路径:

文章链接
题目链接:62.不同路径

思路:

  1. 动态规划
    使用二维数组保存递推结果
    ① dp数组及下标含义
    dp[i][j]:表明从(0, 0)到下标为(i, j)的点有多少条不同的路径
    ② 递推式:
    机器人只能向下或向右移动,因此dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    ③ 初始化:
    应当初始化第一行和第一列均为1
for i in range(m)	dp[i][0] = 0	# 第一列
for i in range(n) dp[0][i] = 0	# 第一列

④ 遍历方式:
从左到右,从上往下遍历
⑤ 举例推导
在这里插入图片描述

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 and n == 1:return 1dp = [[1] * n for _ in range(m)]    # 第一行和第一列路径数都为1dp[0][0] = 1    # 出发点路径数为1for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m - 1][n - 1]

dp数组可以简单为一维数组
按照从左到右,从上到下的遍历顺序
原dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
因此可以简化为一维数组。其中新dp[j]保存的是原dp[i - 1][j]
相当于dp[j]保存的是上一行的数据,从而dp[j] = dp[j] + dp[j - 1]

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 and n == 1:return 1dp = [1] * nfor i in range(1, m):for j in range(1, n):dp[j] += dp[j - 1]return dp[n - 1]
  1. 数论的方法
    从(0, 0)到(m - 1, n - 1)一共 m + n - 2步,其中m - 1步为向下的。因此只要在m + n - 2中选择 m - 1步向下即可,即求组合C_{m + n - 2} ^ {m - 1}
    不能直接分别计算分子、分母后进行除法运算,会溢出,因此需要一边求分子一边对分子进行除法运算
class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 and n == 1:return 1numerator = 1   # 分子denominator = m - 1     # 分母t = m + n - 2count = m - 1while count:numerator *= twhile denominator != 0 and numerator % denominator == 0:numerator = numerator // denominatordenominator -= 1t -= 1count -= 1return numerator

感悟:

简化dp数组以及使用数论的方法求


LeetCode 63.不同路径Ⅱ:

文章链接
题目链接:63.不同路径Ⅱ

思路:

  1. 使用二维数组保存递推的结果
    ① dp数组及下标的含义:
    dp[i][j]:表示从(0, 0)到(i, j)的移动路径中没有障碍的路径数
    ② 递推式:
    机器人还是只能向下或向右移动,因此
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    但是要求路径中不能有障碍,因此上式只能在(i, j)不为障碍时成立
    ③ 初始化:
    还是初始化横向和纵向的,但是遇到障碍后,后面的dp应当都为0
    在这里插入图片描述
    1)第一种初始化
    dp[i][0] = dp[i - 1]0
dp[0][0] = 1
# 初始化第1列,行同理
for i in range(1, m):if obstacleGrid[i][0] == 0:dp[i][0] = dp[i - 1][0]else:dp[i][0] = 0

2)第二种初始化。
dp最开始时初始化为全0,遍历第1列时,遇到非障碍赋值为1,遇到障碍直接退出

dp = [[0] * n for _ in range(m)]
dp[0][0]
for i in range(1, m):if obstacleGrid[i][0] == 0:dp[i][0] = 1else:break 

④ 遍历方式
从左到右,从上到下
⑤ 举例
在这里插入图片描述
需要注意的是,初始化遍历时,第一种遍历方式dp[0][0] = 1,但是出发点是会有障碍的,因此需要先判断出发点是否有障碍再下一步初始化

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:if obstacleGrid[0][0] == 1: # 初始位置就有障碍return 0m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0] * n for _ in range(m)]    # 初始化为0dp[0][0] = 1# 初始化,遇到有障碍物之后的路径数均为0for i in range(1, m):  # 第0列if obstacleGrid[i][0] == 0:dp[i][0] = dp[i - 1][0]for j in range(1, n):  # 第0行if obstacleGrid[0][j] == 0:dp[0][j] = dp[0][j - 1]# 递推for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] == 0:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m - 1][n - 1]
  1. 使用一维数组保存递推的结果
    如果使用一维数组保存递推的结果,实际上一维数组保存的是原二维dp数组中上一行的结果,即一维数组的遍历是按行来的。
    初始化:和二维数组初始化方式相同,但是只初始化第1行
    递推:按行递推遍历时,j从0开始,因为一维数组保存的是原二维数组上一行的结果,因此dp[j] = dp[j] + dp[j - 1]仅在j != 0时成立, j = 0时,dp[j]直接继承上一行的结果不变
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:if obstacleGrid[0][0] == 1:return 0m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [0] * ndp[0] = 1for j in range(1, n):if obstacleGrid[0][j] == 0:dp[j] = 1else:breakfor i in range(1, m):for j in range(n):if obstacleGrid[i][j] == 1:dp[j] = 0elif j != 0:dp[j] += dp[j - 1]return dp[n - 1] 

感悟:

将二维dp数组降为一维dp数组


学习收获:

有障碍时对应的dp数组如何初始化,以及递推式如何变化。
以及将原本的二维dp数组降为一维dp数组时,遍历的话 j 从0开始

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/3861.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

模板

1.非类型模板参数 模板参数分为类型形参与非类型形参(都可以用缺省值) 类型形参:出现在模板参数列表中,跟在class或者typename之类的参数类型名称 非类型形参:就是用一个常量作为类(函数)模板…

diffusion model 学习笔记

条件引导的 diffusion 对于无条件的DDPM 而言 p ( x t ∣ x 0 ) ∼ N ( α t ˉ x 0 , 1 − α t ˉ ⋅ I ) p(x_t | x_0) \sim \mathcal{N}( \sqrt{\bar{\alpha_t}} x_0, 1-\bar{\alpha_t} \cdot \mathrm{I} ) p(xt​∣x0​)∼N(αt​ˉ​ ​x0​,1−αt​ˉ​⋅I) 可以得到…

阿里云高并发测试-Redis缓存机制

创建接口 这里使用的是阿里云提供的接口服务直接做的测试,接口地址 curl http://localhost:8080/initData?tokenAppWithRedis 这里主要通过参数cacheFirstfalse和true来区分是否走缓存,正常的业务机制可能是通过后台代码逻辑自行控制的,这…

设计卷积神经网络CNN为什么不是编程?

上一篇:《搞清楚这个老六的真面目!逐层‘剥开’人工智能中的卷积神经网络(CNN)》 序言:现在让我们开始走进卷积神经网络(CNN)的世界里。和传统编程完全不同,在人工智能的程序代码里…

气象仿真数据在光伏行业里面的作用

选址与规划 确定资源潜力区域:不同地区的太阳能资源、气候条件差异很大。通过对大量的气象仿真数据进行分析,可以准确评估不同地区的太阳辐射强度、日照时长、温度、湿度、风速风向以及降水情况等气象要素。规避潜在风险:一些地区可能存在极…

鸿蒙开发——进程模型与进程通信

1、进程模型 ❓ 什么是进程? 进程是一个正在执行的程序的实例。当我们启动一个程序时,操作系统会创建一个进程,分配给它所需的资源,如内存和CPU时间。每个进程至少有一个线程,即执行线程,负责执行程序的指…

Pod安装软件将CDN改为国内的镜像

1、碰到错误 在pod install的时候碰到以下的下载错误: 文字错误如下: CDN: trunk URL couldnt be downloaded: https://cdn.jsdelivr.net/cocoa/Specs/5/b/d/OpenCV/2.4.11/OpenCV.podspec.json Response: Timeout was reached CDN: trunk URL couldn…

Windows常用命令-病毒

1.常见端口对应的服务 ftp 21 tenlnet 23 80 web 80-89可能是web 443 ssl心脏滴血漏洞以及一些web漏洞测试 445 smb 1433 mssql 1521 oracle 2082/2083 cpanel主机管理系统登陆(国外用的较多) 2222 da虚拟主机管理系统登陆(国外较多) 3128 squid代理默认端口-漫游内…

DDD中的一些基础概念 观点摘录

系统复杂度来源于哪?也就是DDD存在意义 软件系统的复杂性主要体现在三个方面。 隐晦:一是抽象层面的隐晦,抽象系统时,每个人都有自己特定的视角,你需要站在对方的角度才能明白他为什么这么做;其次是实现层…

统信UOS开发环境支持shell

内置了Bash等流行的Shell环境,用户可编写自动化脚本,极大地提高了系统管理和应用开发效率。 文章目录 一、环境部署1. shell开发环境安装2. shell开发环境配置二、代码示例shell开发案例三、常见问题1. 文件处理2. 错误处理3. 跨平台兼容性一、环境部署 1. shell开发环境安装…

使用compare做简单的点云滤波,并另存为文件

一、打开compare软件后,打开一个pcd文件 二、点击显示的pcd文件对象,出现如图黄色框框 三、点击上边的菜单栏的这个标志 四、出现如下图,此时调整红绿蓝就可以简单的做一下背景的滤波操作 五、我调整蓝色按钮后将背景点云去除,点…

布谷语音源码服务器搭建环境及配置流程

布谷语音源码部署环境安装要求(只有在相同的环境下才更容易避免一些不必要的麻烦):●安装Center OS 7.9,我们自己的服务器使用的是7.9建议相同系统,非强制●安装宝塔环境(强烈推荐使用)●安装软…

奥数与C++小学四年级(第二十题 猜猜看)

参考程序代码&#xff1a; #include <iostream> using namespace std;int main() {// 集合 {1, 2, 3, 4, 5, 6, 7, 8}int set[] {1, 2, 3, 4, 5, 6, 7, 8};// 枚举所有可能的 5 个数for (int i 0; i < 8; i) {for (int j i 1; j < 8; j) {for (int k j 1; k…

关于游戏加加不可以在cs2中显示的解决方案

输入的代码如下 -allow_third_party_software 1.打开steam 右键cs2&#xff0c;打开属性。 然后再这里填上这个代码就可以了

QGIS:HCMGIS插件

插件GitHub地址&#xff1a;https://github.com/thangqd/HCMGIS。 以下对HCMGIS插件进行简单介绍&#xff0c;并演示如何进行地图数据下载。 插件简介 HCMGIS - Basemaps, Download OpenData, Batch Converter, VN-2000 Projections, and Field Calculation Utilities for QGI…

康姿百德典雅床垫功效价格双佳,上班族睡眠升级的秘密武器

卓越支撑&#xff0c;透气之选 —— 康姿百德集团公司典雅床垫引领睡眠新风尚 选择一款优质的床垫对于确保良好的睡眠至关重要&#xff0c;尤其是对于每日辛勤工作的上班族而言。一天结束后&#xff0c;躺在舒适的床垫上&#xff0c;享受深度睡眠的美好体验&#xff0c;是最放…

103 - Lecture 3

SQL - Table and Data Part 2 一、Table Constraints Table constraints can be defined when creating tables. But you can also add constraints to an existing table. 1. Syntax of Constraints • General Syntax: CONSTRAINT name TYPE details; • 约束名称是为了以后…

前端 算法 双指针

文章目录 三数之和移动零盛最多水的容器接雨水 三数之和 leetcode 三数之和 题目链接 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有…

nuPlan最新SOTA,香港科技大学发布基于学习决策范围内的规划PlanScope

nuPlan最新SOTA&#xff0c;香港科技大学发布基于学习决策范围内的规划PlanScope Abstract 在自动驾驶的背景下&#xff0c;基于学习的方法在规划模块的开发中表现出了很大的潜力。在规划模块的训练过程中&#xff0c;直接最小化专家驾驶日志与规划输出之间的差异是一种广泛采…

MATLAB实现人工免疫网络算法(Artificial Immune Network Algorithm, AINA)

1. 免疫网络算法简介 生物免疫系统是自然界中最复杂、最有效的自适应系统之一&#xff0c;它能够识别并清除入侵的病原体&#xff0c;同时保持对自身细胞的忍耐。免疫网络算法是一种借鉴生物免疫系统原理和机制的计算模型 2.算法流程 3.MATLAB代码 完整代码见: https://down…