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

代码随想录Day33 LeetCode T62不同路径 LeetCode T63 不同路径II

前言

动规五部曲

1.确定dp数组含义

2.确定递推公式

3.初始化数组

4.确定遍历方式

5.打印dp数组查看分析问题

LeetCode  T62 不同路径

题目链接:62. 不同路径 - 力扣(LeetCode)

题目思路:

注:n行m列而不是m行n列

1.确定dp数组含义

代表到达此下标有多少条路径

2.确定递推公式

因为只能向右或者向下走,所以到达i,j这个点的路径只有从左边和从上面到达,所以到达这个的途径数就是左边的数和上面的数之和.

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

3.初始化数组

初始化的时候应该将左边边界和上面边界都初始化为1,因为只有一条路径能到达

        for(int i = 0;i<m;i++){dp[i][0] = 1;}for(int i = 0;i<n;i++){dp[0][i] = 1;}

4.确定遍历方式

此题目跟遍历顺序无关,顺序遍历即可

5.打印dp数组查看分析问题

遇见问题可以打印dp数组并推导尝试是否有问题

最后直接返回右下角的值即可

题目代码:

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i = 0;i<m;i++){dp[i][0] = 1;}for(int i = 0;i<n;i++){dp[0][i] = 1;}
//记得从下标1,1开始哦,不然就越界了for(int i = 1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}

LeetCode T63 不同路径II

题目链接:63. 不同路径 II - 力扣(LeetCode)

题目思路:

1.确定dp数组含义

此时的dp数组也是代表和上一题一样的含义,表示有多少条路径能到达这个坐标

2.确定递推公式

注:这里如果遇到障碍,也就是1的情况,我们就让dp这个点取得0,不然就是和上文一样的递推公式

dp[i][j] = (obstacleGrid[i][j] == 0)?dp[i-1][j] + dp[i][j-1]:0;

3.初始化数组

这里初始化在边界遇到障碍的时候就是代表后面的下标都是到达不了的地方,所以就不进行赋值

注意:如果起点或者终点为障碍,就直接返回0

4.确定遍历方式

顺序遍历即可

5.打印dp数组查看分析问题

题目代码:

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];//起点和终点为障碍if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1){return 0;}for(int i = 0;i<m && obstacleGrid[i][0] == 0;i++){dp[i][0] = 1;}for(int i = 0;i<n && obstacleGrid[0][i] == 0;i++){dp[0][i] = 1;}for(int i = 1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = (obstacleGrid[i][j] == 0)?dp[i-1][j] + dp[i][j-1]:0;}}return dp[m-1][n-1];}
}

相关文章:

代码随想录Day33 LeetCode T62不同路径 LeetCode T63 不同路径II

前言 动规五部曲 1.确定dp数组含义 2.确定递推公式 3.初始化数组 4.确定遍历方式 5.打印dp数组查看分析问题 LeetCode T62 不同路径 题目链接:62. 不同路径 - 力扣&#xff08;LeetCode&#xff09; 题目思路: 注:n行m列而不是m行n列 1.确定dp数组含义 代表到达此下标有多少条…...

【计算机网络】分层模型和应用协议

网络分层模型和应用协议 1. 分层模型 1.1 五层网络模型 网络要解决的问题是&#xff1a;两个程序之间如何交换数据。 四层&#xff1f;五层&#xff1f;七层&#xff1f; 2. 应用层协议 2.1 URL URL&#xff08;uniform resource locator&#xff0c;统一资源定位符&#…...

Python框架之Flask入门和视图

一、Flask入门和视图 需要安装Pycharm专业版 1. Flask简介 Python后端的2个主流框架 Flask 轻量级框架Django 重型框架 Flask是一个基于Python实现的web开发微框架 官方文档&#xff1a;https://flask.palletsprojects.com/ 中文文档&#xff1a;https://dormousehole.readthe…...

streamWriter.WriteLine

streamWriter.WriteLine写入文件有回车行 using (System.IO.StreamWriter streamWriter new System.IO.StreamWriter("D:\123.txt", false, System.Text.Encoding.Default)) { streamWriter.Write(str.Replace("…...

一键添加色彩变幻效果,视频剪辑从未如此简单!

在视频制作过程中&#xff0c;给视频添加特效是必不可少的环节。而其中&#xff0c;色彩变幻效果作为一种常用的特效&#xff0c;能够为视频增添独特的氛围和视觉冲击力。然而&#xff0c;对于许多初学者来说&#xff0c;如何批量给视频添加色彩变幻效果特效功能却是一个难题。…...

Linux的简介和环境搭建

简介 Linux是一套免费使用和自由传播的类Unix操作系统&#xff0c;是一个基于POSIX和Unix的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的Unix工具软件、应用程序和网络协议。它支持32位和64位硬件。Linux继承了Unix以网络为核心的设计思想&#xff0c;是一个…...

你看现在的程序员,是怎么解bug的

大家好&#xff0c;我是伍六七。 干程序员的都会碰到各种各样的 bug&#xff0c;有的 bug 我们看一眼、或者多看几眼就能看出来问题。 但是&#xff0c;也有很多问题&#xff0c;我们看不出来&#xff0c;这个时候&#xff0c;我们不妨把我们的代码扔给 GPT&#xff0c;看看它…...

CSS3背景样式

在CSS 2.1中&#xff0c;background属性的功能还无法满足设计的需求&#xff0c;为了方便设计师更灵活地设计需要的网页效果&#xff0c;CSS3在原有background基础上新增了一些功能属性&#xff0c;可以在同一个对象内叠加多个背景图像&#xff0c;可以改变背景图像的大小尺寸&…...

JAVA同城服务同城圈子真人躲猫猫系统的玩法流程

在现在科技的发展和互联网的普及&#xff0c;线上社交游戏在人们的生活中占据了越来越重要的地位。JAVA同城服务同城圈子真人躲猫猫系统就是一种结合了线上社交和线下实体位置服务的全新游戏模式。在这个游戏中&#xff0c;玩家们可以在同一城市中寻找隐藏的对手&#xff0c;体…...

C++继承——圆形和圆柱体

C继承 Circular圆形类 /*圆形类*/ class Circular { private:const static double PI;double R 0; public:Circular() default;Circular(double r);double GetArea(); /*圆面积*/double GetGirth(); /*圆周长*/ }; const double Circular::PI 3.14;Circular::Circula…...

致远OA wpsAssistServlet任意文件上传漏洞复现 [附POC]

文章目录 致远OA wpsAssistServlet任意文件上传漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 0x06 修复建议 致远OA wpsAssistServlet任意文件上传漏洞复现 [附POC] 0x01 前言 免责声明&#xff1a;请勿利用…...

Java规则引擎2.1.8版本新增功能说明

规则引擎更新功能 新增: 1.决策结束节点新增结果导出excel功能&#xff1b; 在决策流程的结束节点&#xff0c;可以将决策结果导出为Excel文件。这个功能为用户提供了更多的灵活性和便利性&#xff0c;使他们能够轻松地将决策结果数据进行进一步的分析和处理。 2.新增公有变…...

系列四十、请谈一下Spring中事务的传播行为

一、概述 事务的传播行为指的是当一个事务方法被另一个事务方法调用时&#xff0c;这个事务方法应该如何进行。事务的传播行为至少发生在两个事务方法的嵌套调用中才会出现。 二、传播行为分类...

kubectl详解

陈述式资源管理方法&#xff1a; 1.kubernetes 集群管理集群资源的唯一入口是通过相应的方法调用 apiserver 的接口 2.kubectl 是官方的CLI命令行工具&#xff0c;用于与 apiserver 进行通信&#xff0c;将用户在命令行输入的命令&#xff0c;组织并转化为 apiserver 能识别的信…...

QT通过url下载http地址下的文件(文件夹)

前言 之前只写过通过http协议通信&#xff0c;没有写过下载http地址中的文件或者文件夹&#xff0c;了解一下在QT下如何下载。 其实很简单&#xff0c;同使用协议通信相同的是&#xff0c;创建QNetworkAccessManager和QNetworkRequest&#xff0c;设置QNetworkRequest的url&a…...

测试实施运维必备知识点

Linux常用命令 ip addr 查看ip地址信息 ping 测试物理机是否联网 dhclient 让CentOS 7自动获取一个IP地址 vim 编辑纯文本文件 who 查看是否还有其他人在登录 find 在文件系统中搜索某文件 -name filename&#xff1a; 表示直接查找该文件名的文件 -type filetype&#xff1a;…...

RTSP/Onvif安防视频平台EasyNVR接入EasyNVS,出现Login error报错的解决方法

安防视频监控汇聚EasyNVR平台&#xff0c;是基于RTSP/Onvif协议的安防视频平台&#xff0c;可支持将接入的视频流进行全平台、全终端分发&#xff0c;分发的视频流包括RTSP、RTMP、HTTP-FLV、WS-FLV、HLS、WebRTC等格式。为了满足用户的集成与二次开发需求&#xff0c;我们也提…...

在Linux环境下远程访问MeterSphere开源测试平台

文章目录 前言1. 安装MeterSphere2. 本地访问MeterSphere3. 安装 cpolar内网穿透软件4. 配置MeterSphere公网访问地址5. 公网远程访问MeterSphere6. 固定MeterSphere公网地址 前言 MeterSphere 是一站式开源持续测试平台, 涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&am…...

ARPG----C++学习记录02 Section6位置,偏移,函数

设置actor位置 这一句代码就可以更改位置和旋转 给位置添加偏移offset 将debug的持久都设置为false,在tick中调用&#xff0c;球就会动。这是每帧移动&#xff0c;所以移动速度和帧率有关&#xff0c;需要更改 void Aitem::Tick(float DeltaTime) {Super::Tick(DeltaTime);Ad…...

怎么在现货黄金交易过程中高效设置止损?

投资市场中的风险具有客观及普遍性&#xff0c;现货黄金买卖也是如此&#xff0c;作为典型的国际性交易产品之中&#xff0c;在现货黄金买卖过程中人们要灵活应对行情变化&#xff0c;从中争取盈利空间。而设置止损就是防止风险扩大的一条有效措施&#xff0c;所以炒金者们应当…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...