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

代码随想录算法训练营第三十二天 | 509. 斐波那契数 | 70. 爬楼梯 | 746. 使用最小花费爬楼梯

Day 32 总结

  • 自己实现中遇到哪些困难
  • 今日收获,记录一下自己的学习时间
    • 12:30 - 21:30

理论基础

代码随想录

  • 动态规划

    • 问题有很多的重叠子问题需要解决,状态涉及推导

  • DP 5部曲

    • DP数组含义

    • 状态转移公式

    • dp数组初始化

    • 数组遍历顺序

    • 举例推导

视频:从此再也不怕动态规划了,动态规划解题方法论大曝光 !| 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili

509. 斐波那契数

代码随想录

视频:手把手带你入门动态规划 | LeetCode:509.斐波那契数_哔哩哔哩_bilibili

题目链接:509. 斐波那契数 - 力扣(LeetCode)

题目描述:

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

实现思路:

为什么使用动态规划:计算 F(n)  的时候需要计算 F(n-1) F(n-2), 在计算他们的时候有包含重复的计算过程,所以需要对中间的计算结果进行保存。

dp数组:dp[i] 代表第 n 位斐波那契数的具体值

推导公式:dp[i] = dp[i-1] + dp[i-2]

初始化:i-2 >=0 , i-1 >=0, 初始化 dp[0] = 0 和 dp[1] = 1

遍历顺序:从 2 开始遍历

代码实现:

class Solution {public int fib(int n) {if (n<=1) {return n;}int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;for (int i=2; i<n+1; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

70. 爬楼梯

代码随想录

视频:带你学透动态规划-爬楼梯(对应力扣70.爬楼梯)| 动态规划经典入门题目_哔哩哔哩_bilibili

题目链接:70. 爬楼梯 - 力扣(LeetCode)

题目描述:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

实现思路:

为什么使用动态规划:爬第N层楼梯的方式,等于 爬N-1层的方式 + 爬N-2层的方式,因为可以选择从下面两层任意一层爬上来。但是计算下面楼层爬的方式的时候,会包含重复的计算,所以使用动态规划。

dp数组:dp[i] 代表爬第 i 层楼梯的方式数量

推导公式;dp[i] = dp[i-1] + dp[i-2]

初始化:i-1>=0 ,i-2>=0, i>=2需要初始化dp[0],dp[1]

遍历顺序:从2开始

代码实现:

class Solution {public int climbStairs(int n) {if (n <= 2) return n;int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for (int i=2; i<=n; i++)dp[i] = dp[i-1] + dp[i-2];return dp[n];}
}

746. 使用最小花费爬楼梯

代码随想录

视频讲解:动态规划开更了!| LeetCode:746. 使用最小花费爬楼梯_哔哩哔哩_bilibili

题目链接:746. 使用最小花费爬楼梯 - 力扣(LeetCode)

题目描述:

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

实现思路:

为什么使用动态规划:爬上台阶n可以从 n-1 爬上来,也可以从n-2爬上来,选择费用最低的方式即可。计算n-1的费用和n-2的费用时,包含重复计算,所以使用动态规划。

dp数组:dp[i] 代表第i层楼梯累计的费用

推导公式:dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

初始化:需要初始化 dp[0] dp[1]

遍历顺序: 从2开始

代码实现:

class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length+1];dp[0] = 0;dp[1] = 0;for (int i=2; i<=cost.length; i++) {dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);}return dp[cost.length];}
}

相关文章:

代码随想录算法训练营第三十二天 | 509. 斐波那契数 | 70. 爬楼梯 | 746. 使用最小花费爬楼梯

Day 32 总结 自己实现中遇到哪些困难今日收获&#xff0c;记录一下自己的学习时间 12:30 - 21:30 理论基础 代码随想录 动态规划 问题有很多的重叠子问题需要解决&#xff0c;状态涉及推导 DP 5部曲 DP数组含义 状态转移公式 dp数组初始化 数组遍历顺序 举例推导 视频&a…...

Flink常见面试题

1、Flink 的四大特征&#xff08;基石&#xff09; 2、Flink 中都有哪些 Source&#xff0c;哪些 Sink&#xff0c;哪些算子&#xff08;方法&#xff09; 预定义Source 基于本地集合的source&#xff08;Collection-based-source&#xff09; 基于文件的source&#xff08;…...

SpringCloud之Config:从基础到高级应用

目录 一、SpringCloud Config 简介1、SpringCloud Config 概述&#xff08;1&#xff09;核心概念&#xff08;2&#xff09;SpringCloud Config 的特点&#xff08;3&#xff09;应用场景&#xff08;4&#xff09;工作原理&#xff08;5&#xff09;优势&#xff08;6&#x…...

redis 底层数据结构

概述 Redis 6 和 Redis 7 之间对比&#xff1a; Redis6 和 Redis7 最大的区别就在于 Redis7 已经用 listpack 替代了 ziplist. 以下是基于 Redis 7基础分析。 RedisObject Redis是⼀个<k,v>型的数据库&#xff0c;其中key通常都是string类型的字符串对象&#xff0c;⽽…...

机器学习之RLHF(人类反馈强化学习)

RLHF(Reinforcement Learning with Human Feedback,基于人类反馈的强化学习) 是一种结合人类反馈和强化学习(RL)技术的算法,旨在通过人类的评价和偏好优化智能体的行为,使其更符合人类期望。这种方法近年来在大规模语言模型(如 OpenAI 的 GPT 系列)训练中取得了显著成…...

openwrt利用nftables在校园网环境下开启nat6 (ipv6 nat)

年初写过一篇openwrt在校园网环境下开启ipv6 nat的文章&#xff0c;利用ip6tables控制ipv6的流量。然而从OpenWrt22版本开始&#xff0c;系统内置的防火墙变为nftables&#xff0c;因此配置方法有所改变。本文主要参考了OpenWRT使用nftables实现IPv6 NAT 这篇文章。 友情提示 …...

Vue3+node.js实现注册

文章目录 前端代码实现后端代码实现 效果图 前端代码实现 <template><div class"register-container"><el-card class"register-card"><template #header><div class"card-header"><span>注册</span&…...

LabVIEW将TXT文本转换为CSV格式(多行多列)

在LabVIEW中&#xff0c;将TXT格式的文本文件内容转换为Excel格式&#xff08;即CSV文件&#xff09;是一项常见的数据处理任务&#xff0c;适用于将以制表符、空格或其他分隔符分隔的数据格式化为可用于电子表格分析的形式。以下是将TXT文件转换为Excel&#xff08;CSV&#x…...

SpringBoot源码-Spring Boot启动时控制台为何会打印logo以及自定义banner.txt文件控制台打印

1.当我们启动一个SpringBoot项目的时候&#xff0c;入口程序就是main方法&#xff0c;而在main方法中就执行了一个run方法。 SpringBootApplication public class StartApp {public static void main(String[] args) {// testSpringApplication.run(StartApp.class);} }publi…...

【笔记】软技能

硬技能&#xff1a;操控世界的能力&#xff0c;处理对象为【物】。软技能&#xff1a;影响他人的能力&#xff0c;处理对象为【人】。软技能包括一个人的情商、个性、社交礼仪、沟通、语言、个人习惯&#xff0c;还有解决问题的能力、领导能力、时间管理能力等一切非技术能力。…...

试题转excel;试题整理工具;试卷转excel;word转excel

一、问题描述 我父亲是一名教师&#xff0c;偶尔会需要将试卷转excel&#xff0c;方便管理处理一些特别重要的题目 于是&#xff0c;就抽空写一个专门将试题转excel的工具&#xff0c;便于各位教师从业者和教育行业的朋友更好的整理试题&#xff0c;减少一点重复枯燥的工作 …...

【热门主题】000072 分布式数据库:开启数据管理新纪元

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 【热…...

常见靶场的搭建

漏洞靶场 渗透测试&#xff08;漏洞挖掘&#xff09;切忌纸上谈兵&#xff0c;学习渗透测试&#xff08;漏洞挖掘&#xff09;知识的过程中&#xff0c;我们通常需要一个包含漏洞的测试环境来进行训练。而在非授权情况下&#xff0c;对于网站进行渗透测试攻击&#xff0c;是触及…...

C语言——链表

1 链表基础 1 什么是链表 &#xff01;&#xff01;&#xff01;链表相当于多个结构体变量链接在一起&#xff01;&#xff01;&#xff01; //链表节点结构 struct Node //数据域和指针域 {int data; //数据域//struct Student data;数据尽量不写在链表结构体里面&#xf…...

【经典】星空主题的注册界面HTML,CSS,JS

目录 界面展示 完整代码 说明&#xff1a; 这是一个简单的星空主题的注册界面&#xff0c;使用了 HTML 和 CSS 来实现一个背景为星空效果的注册页面。 界面展示 完整代码 <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8&…...

94.【C语言】解析预处理(2)

目录 1.带有副作用的宏参数 代码 一个判断最大值的宏代码 运行结果 分析 "副作用"的解释 2.宏替换规则 解释 3.宏和函数的对比 附一张对比表 承接93.【C语言】解析预处理(1)文章 1.带有副作用的宏参数 代码 一个判断最大值的宏代码 #define MAX(a, b) (…...

(数据结构与算法)如何提高学习算法的效率?面试算法重点有哪些?面试需要哪些能力?

面试官眼中的求职者 通过对你算法的考察&#xff01;&#xff01;&#xff01;&#xff01; 缩进太多&#xff01;&#xff01;一般不要超过三层&#xff01;&#xff01;&#xff01;缩进越少&#xff0c;bug越少&#xff1b;逻辑比较复杂&#xff0c;把这些包装成为函数&…...

STM32 BootLoader 刷新项目 (十二) Option Byte之FLASH_OPTCR-命令0x58

STM32 BootLoader 刷新项目 (十二) Option Byte之FLASH_OPTCR-命令0x58 STM32F407芯片的OPTION Byte全面解析 STM32F407芯片是STMicroelectronics推出的一款功能强大的微控制器&#xff0c;广泛应用于工业控制、通信和消费电子等领域。其中&#xff0c;OPTION Byte&#xff0…...

MySQL主从复制

华子目录 实验环境准备修改配置文件 实验主开启bin-log日志创建用于主从复制的用户master配置salve配置 测试 添加一台新的slave&#xff0c;如何实现数据的全部同步呢什么环境下主比较多&#xff0c;什么环境下从比较多&#xff1f;延迟复制测试 并行复制gtid模式未启用gtid时…...

贝叶斯统计:高斯分布均值μ的后验分布推导

使用贝叶斯统计方法 均值 ( μ \mu μ ) 的后验分布解析 在贝叶斯统计中&#xff0c;后验分布表示在观察到数据后&#xff0c;对参数的更新后的信念。本篇文章将结合高斯分布的假设&#xff0c;详细解析均值 ( μ \mu μ ) 的后验分布推导过程&#xff0c;并对 ( μ \mu μ…...

linux常用指令都是工作中遇到的

前端打war包 jar -cvf dist.war *创建 WAR 文件的命令 jar -cvf dist.war * 用于将当前目录下的所有文件和文件夹打包成一个名为 dist.war 的 WAR 文件。以下是该命令的详细解释&#xff1a; jar: Java Archive 工具&#xff0c;用于创建 JAR、WAR 或 EAR 文件。 -c: 创建新的…...

亚马逊自研大语言模型 Olympus 即将亮相,或将在 LLM 竞赛中掀起新波澜

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

droppath

DropPath 是一种用于正则化深度学习模型的技术&#xff0c;它在训练过程中随机丢弃路径&#xff08;或者说随机让某些部分的输出变为零&#xff09;&#xff0c;从而增强模型的鲁棒性和泛化能力。 代码解释&#xff1a; import torch import torch.nn as nn # 定义 DropPath…...

通信与网络安全之IPSEC

IPSec&#xff08;IP Security&#xff09;是IETF制定的为保证在Internet上传送数据的安全保密性能的三层隧道加密协议。IPSec在网络层对IP报文提供安全服务。IPSec协议本身定义了如何在IP数据包中增加字段来保证IP包的完整性、 私有性和真实性&#xff0c;以及如何加密数据包。…...

Linux内核编译流程(Ubuntu24.04+Linux Kernel 6.8.12)

万恶的拯救者&#xff0c;使用Ubuntu没有声音&#xff0c;必须要自己修改一下Linux内核中的相关驱动逻辑才可以&#xff0c;所以被迫学习怎么修改内核&编译内核&#xff0c;记录如下 准备工作 下载Linux源码&#xff1a;在Linux发布页下载并使用gpg签名验证 即&#xff1a…...

什么是GAN?

一、基本概念 生成对抗网络&#xff08;Generative Adversarial Network&#xff0c;GAN&#xff09;是一种由两个神经网络共同组成深度学习模型&#xff1a;生成器&#xff08;Generator&#xff09;和判别器&#xff08;Discriminator&#xff09;。这两个网络通过对抗的方式…...

torch_geometric使用手册-Creating Graph Datasets(专题四)

虽然 PyG 已经提供了很多有用的数据集,但你可能希望创建自己的数据集,使用自己收集的数据或非公开的数据。 自己实现数据集是非常简单的,你可能想查看源代码,了解各种数据集是如何实现的。然而,这里简要介绍一下如何设置你自己的数据集。 我们提供了两个抽象类用于数据集…...

编程语言之Python

Python是一种高级编程语言&#xff0c;自其诞生以来&#xff0c;便因其简洁明了的语法、强大的功能和广泛的应用领域而备受青睐。以下是对Python的详细介绍&#xff0c;包括其历史、特点、应用领域&#xff0c;以及通过代码示例展示其语法、库、函数等关键概念。同时&#xff0…...

【Go】-调度器简介

目录 数据结构 G M P 调度器启动 创建 Goroutine 初始化结构体 运行队列 调度信息 调度循环 小结 数据结构 Go的运行时调度器的三个重要组成部分 — 线程 M、Goroutine G 和处理器 P&#xff1a; 图 6-29 Go 语言调度器 G — 表示 Goroutine&#xff0c;它是一个待…...

在Ubuntu 22.04上设置Python 3的Jupyter Notebook

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 简介 Jupyter Notebook 是一个作为 Web 应用程序的交互式计算命令 shell。该工具可与多种语言一起使用&#xff0c;包括 Python、Julia…...

通讯专题4.1——CAN通信之计算机网络与现场总线

从通讯专题4开始&#xff0c;来学习CAN总线的内容。 为了更好的学习CAN&#xff0c;先从计算机网络与现场总线开始了解。 1 计算机网络体系的结构 在我们生活当中&#xff0c;有许多的网络&#xff0c;如交通网&#xff08;铁路、公路等&#xff09;、通信网&#xff08;电信、…...

将jar包导入maven

1.将jar包放repository 2.执行命令&#xff1a;mvn install:install-file -DgroupIdcom.oracle -DartifactIdojdbc7 -Dversion12.1.0.2 -Dpackagingjar -DfileD:\dev\utils\idea\repository\ojdbc7.jar -Dfile: 指定要安装的JAR文件的路径。 -DgroupId: 指定项目的groupId。 -…...

Mysql实现定时自动备份(Windows环境)

一.新建数据库备份目录 二.新建批处理文件 创建批处理文件mysql_backup.bat echo off set BACKUP_DIRD:\backup set MYSQL_USERroot set MYSQL_PASS123456 set MYSQL_HOSTlocalhost set DATABASE_NAMEphoenix set DATE%date:~0,4%-%date:~5,2%-%date:~8,2%_%time:~0,2%-%time…...

kafka数据在服务端时怎么写入的

学习背景 接着上篇&#xff0c;我们来聊聊kafka数据在服务端怎么写入的 服务端写入 在介绍服务端的写流程之前&#xff0c;我们先要理解服务端的几个角色之间的关系。 假设我们有一个由3个broker组成的kafka集群&#xff0c;我们在这个集群上创建一个topic叫做shitu-topic&…...

2024算法基础公选课练习七(BFS1)

一、前言 还是偏基础的bfs&#xff0c;但是有几个题不是很好写 二、题目总览 三、具体题目 3.1 问题 A: 数据结构-队列-奇怪的电梯 我的代码 可以看成求一维平面的bfs最短路 #include <bits/stdc.h> using i64 long long; using pii std::pair<int,int>; co…...

算法刷题Day1

BM47 寻找第k大 第一天就随便记录吧&#xff0c;万事开头难&#xff0c;我好不容易开的头&#xff0c;就别难为自己&#xff0c;去追求高质量了。嘿嘿嘿 题目 传送门 解题思路一&#xff1a;维护一个大小为k的最小堆。最后返回堆顶元素。 代码&#xff1a; # # 代码中的类名…...

你还没有将 Siri 接入GPT对话功能吗?

由于各种原因&#xff0c;国内ios用户目前无缘自带 AI 功能&#xff0c;但是这并不代表国内 ios 无法接入 AI 功能&#xff0c;接下来手把手带你为iPhone siri 接入 gpt 对话功能。 siri 接入 chatGPT 暂时还无法下载 ChatGPT app&#xff0c;或者没有账号的读者可以直接跳到…...

LabVIEW 标准状态机设计模式

LabVIEW 标准状态机设计模式 LabVIEW 软件框架介绍LabVIEW编程模式及其应用分析状态机模式的类型分析标准状态机设计模式及状态机应用学习顺序结构它的一个缺点是什么&#xff1f; 状态机结构 LabVIEW 软件框架介绍 源于虚拟仪器技术的LabVIEW程序设计语言&#xff0c;从被创建…...

Scala学习记录,统计成绩

统计成绩练习 1.计算每个同学的总分和平均分 2.统计每个科目的平均分 3.列出总分前三名和单科前三名&#xff0c;并保存结果到文件中 解题思路如下&#xff1a; 1.读入txt文件&#xff0c;按行读入 2.处理数据 &#xff08;1&#xff09;计算每个同学的总分平均分 import s…...

使用 client-go 实现 Kubernetes 节点 Drain:详解与实战教程

在 Kubernetes 中使用 client-go 实现 drain 功能涉及多个步骤&#xff0c;需要模仿 kubectl drain 的行为。这包括将节点标记为不可调度&#xff08;cordon&#xff09;、驱逐 Pod&#xff0c;并处理 DaemonSet 和不可驱逐 Pod 的逻辑。以下是实现 drain 的主要步骤&#xff1…...

C#VB.Net项目一键多国语言显示

如何在项目什么都不做一键支持多国语言显示 开始我们的一键快捷使用之旅 01.创建多语言项目 02.一键批量窗口开启本地化,添加选中内容添加Mu方法 03.一键快捷翻译 04.运行查看效果 01.创建多语言项目 创建多语言项目前,请先下载安装&#xff0c;注册并登录. 为了便于演示这…...

【关闭or开启电脑自带的数字键盘】

目录 一、按数字键盘左上角的按键【NumLK Scroll】 二、修改注册表中数字键盘对应的数值【InitialKeyboardIndicators】 1、步骤&#xff1a; 2、知识点&#xff1a; 一、按数字键盘左上角的按键【NumLK Scroll】 这是最简单快捷的方法。 关闭后若想开启&#xff0c;再按一…...

如何在Bash中等待多个子进程完成,并且当其中任何一个子进程以非零退出状态结束时,使主进程也返回一个非零的退出码?

文章目录 问题回答参考 问题 如何在 Bash 脚本中等待该脚本启动的多个子进程完成&#xff0c;并且当这其中任意一个子进程以非零退出码结束时&#xff0c;让该脚本也返回一个非零的退出码&#xff1f; 简单的脚本: #!/bin/bash for i in seq 0 9; docalculations $i & d…...

Asio2网络库

header only,不依赖boost库,不需要单独编译,在工程的Include目录中添加asio2路径,在源码中#include <asio2/asio2.hpp>即可使用;支持tcp, udp, http, websocket, rpc, ssl, icmp, serial_port;支持可靠UDP(基于KCP),支持SSL;TCP支持各种数据拆包功能(单个字符或字符串或用…...

Uniapp 微信小程序内打开web网页

技术栈&#xff1a;Uniapp Vue3 简介 实际业务中有时候会需要在本微信小程序内打开web页面&#xff0c;这时候可以封装一个路由页面专门用于此场景。 在路由跳转的时候携带路由参数&#xff0c;拼接上web url&#xff0c;接收页面进行参数接收即可。 实现 webview页面 新…...

学习线性表_3

单链表的删除 直接删除即可删除后要free //删除第i个位置的元素 //删除时L是不会变的&#xff0c;所以不需要加引用 bool ListDelect(LinkList L,int i) {//i 1,即删除头指针//拿到要删除结点的前一个结点LinkList p GetElem(L,i-1);if(NULLp){return false;}//拿到要删除的结…...

智能桥梁安全运行监测系统守护桥梁安全卫士

一、方案背景 桥梁作为交通基础设施中不可或缺的重要组成部分&#xff0c;其安全稳定的运行直接关联到广大人民群众的生命财产安全以及整个社会的稳定与和谐。桥梁不仅是连接两地的通道&#xff0c;更是经济发展和社会进步的重要纽带。为了确保桥梁的安全运行&#xff0c;桥梁安…...

Arrays.asList()新增报错,该怎么解决

一、前言 在 Java 开发中&#xff0c;Arrays.asList() 是一个常用的工具方法&#xff0c;它允许开发者快速将数组转换为列表。尽管这个方法非常方便&#xff0c;但许多开发者在使用时可能会遭遇一个常见的错误&#xff1a;尝试向由 Arrays.asList() 返回的列表中添加元素时抛出…...

28.UE5实现对话系统

目录 1.对话结构的设计&#xff08;重点&#xff09; 2.NPC对话接口的实现 2.1创建类型为pawn的蓝图 2.2创建对话接口 3.对话组件的创建 4.对话的UI设计 4.1UI_对话内容 4.2UI_对话选项 4.3UI_对话选项框 5.对话组件的逻辑实现 通过组件蓝图&#xff0c;也就是下图中的…...

会议直击|美格智能亮相2024紫光展锐全球合作伙伴大会,融合5G+AI共拓全球市场

11月26日&#xff0c;2024紫光展锐全球合作伙伴大会在上海举办&#xff0c;作为紫光展锐年度盛会&#xff0c;吸引来自全球的众多合作伙伴和行业专家、学者共同参与。美格智能与紫光展锐竭诚合作多年&#xff0c;共同面向5G、AI和卫星通信为代表的前沿科技&#xff0c;聚焦技术…...