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

LeetCode算法刷题(python) Day41|09动态规划|理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

目录

  • 动规五部曲
  • LeetCode 509. 斐波那契数
  • LeetCode 70. 爬楼梯
  • LeetCode 746. 使用最小花费爬楼梯

动规五部曲

  1. 确定dp数组以及下标的含义
  2. 确定递归公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

LeetCode 509. 斐波那契数

力扣题目链接

本题最直观是用递归方法

class Solution:def fib(self, n: int) -> int:if n == 0: return 0elif n == 1: return 1else:return self.fib(n-1) + self.fib(n-2)

当然,本题也可以用动态规划,是最简单的问题

class Solution:def fib(self, n: int) -> int:dp = [0] * (n+1)if n > 0:dp[1] = 1for i in range(2, n+1):dp[i] = dp[i-1] + dp[i-2]return dp[-1]

LeetCode 70. 爬楼梯

力扣题目链接
本题代码实际跟上一题斐波那契数一样。
如果是1个台阶,只有一种方法,如果有两个台阶也只有两种方法,这就是动规的初始值。
n>2时,到达第n个台阶的最后一步可以爬1个台阶也可以爬2个台阶,如果爬1个台阶,那么前面的种数就跟n-1个台阶的情况一样;如果爬2个台阶,那么跟n-2个台阶的情况一样。
所以n个台阶的方法=n-1个台阶的方法数+n-2个台阶的方法数。这不就是不同初始值的斐波那契数列吗!

class Solution:def climbStairs(self, n: int) -> int:if n <= 2:return ndp = [0] * ndp[0] = 1dp[1] = 2for i in range(2, n):dp[i] = dp[i-1] + dp[i-2]return dp[-1]

LeetCode 746. 使用最小花费爬楼梯

力扣题目链接

  1. 确定dp数组以及下标的含义:到达第i个台阶的最小花费
  2. 确定递归公式:dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
  3. dp数组如何初始化:可以从下标为 0 或下标为 1 的台阶开始爬楼梯,意味着dp[0], dp[1]初始值都为0
  4. 确定遍历顺序:从前向后遍历
  5. 举例推导dp数组
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0] * (len(cost) + 1)for i in range(2, len(cost)+1):dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])return dp[-1]

今日毕!

相关文章:

LeetCode算法刷题(python) Day41|09动态规划|理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

目录 动规五部曲LeetCode 509. 斐波那契数LeetCode 70. 爬楼梯LeetCode 746. 使用最小花费爬楼梯 动规五部曲 确定dp数组以及下标的含义确定递归公式dp数组如何初始化确定遍历顺序举例推导dp数组 LeetCode 509. 斐波那契数 力扣题目链接 本题最直观是用递归方法 class Sol…...

Spring(四)

1、Spring6整合JUnit 1、JUnit4 User类: package com.songzhishu.spring.bean;import org.springframework.beans.factory.annotation.Value; import org.springframework.stereotype.Component;/*** BelongsProject: Spring6* BelongsPackage: com.songzhishu.spring.bean*…...

2023-10-8讯飞大模型部署2024秋招后端一面(附详解)

1 mybatis的mapper是什么东西 在MyBatis中&#xff0c;mapper是一个核心概念&#xff0c;它起到了桥梁的作用&#xff0c;连接Java对象和数据库之间的数据。具体来说&#xff0c;mapper可以分为以下两个部分&#xff1a; Mapper XML文件&#xff1a; 这是一个XML文件&#xff…...

如何为 Elasticsearch 创建自定义连接器

了解如何为 Elasticsearch 创建自定义连接器以简化数据摄取过程。 作者&#xff1a;JEDR BLASZYK Elasticsearch 拥有一个摄取工具库&#xff0c;可以从多个来源获取数据。 但是&#xff0c;有时你的数据源可能与 Elastic 现有的提取工具不兼容。 在这种情况下&#xff0c;你可…...

Debian11 安装 OpenJDK8

1. 下载安装包 wget http://snapshot.debian.org/archive/debian-security/20220210T090326Z/pool/updates/main/o/openjdk-8/openjdk-8-jdk_8u322-b06-1~deb9u1_amd64.deb wget http://snapshot.debian.org/archive/debian-security/20220210T090326Z/pool/updates/main/o/op…...

[Machine Learning][Part 6]Cost Function代价函数和梯度正则化

目录 拟合 欠拟合 过拟合 正确的拟合 解决过拟合的方法&#xff1a;正则化 线性回归模型和逻辑回归模型都存在欠拟合和过拟合的情况。 拟合 来自百度的解释&#xff1a; 数据拟合又称曲线拟合&#xff0c;俗称拉曲线&#xff0c;是一种把现有数据透过数学方法来代入一条…...

工业自动化编程与数字图像处理技术

工业自动化编程与数字图像处理技术 编程是计算机领域的基础技能&#xff0c;对于从事软件开发和工程的人来说至关重要。在工业自动化领域&#xff0c;C/C仍然是主流的编程语言&#xff0c;特别是用于工业界面(GUI)编程。工业界面是供车间操作员使用的&#xff0c;使用诸如Hal…...

JY61P.C

/** File Name : JY61P.cDescription : attention © Copyright (c) 2020 STMicroelectronics. All rights reserved.This software component is licensed by ST under Ultimate Liberty licenseSLA0044, the “License”; You may not use this file except in complian…...

Go编程:使用 Colly 库下载Reddit网站的图像

概述 Reddit是一个社交新闻网站&#xff0c;用户可以发布各种主题的内容&#xff0c;包括图片。本文将介绍如何使用Go语言和Colly库编写一个简单的爬虫程序&#xff0c;从Reddit网站上下载指定主题的图片&#xff0c;并保存到本地文件夹中。为了避免被目标网站反爬&#xff0c…...

高性能日志脱敏组件:已支持 log4j2 和 logback 插件

项目介绍 日志脱敏是常见的安全需求。普通的基于工具类方法的方式&#xff0c;对代码的入侵性太强&#xff0c;编写起来又特别麻烦。 sensitive提供基于注解的方式&#xff0c;并且内置了常见的脱敏方式&#xff0c;便于开发。 同时支持 logback 和 log4j2 等常见的日志脱敏…...

一文读懂PostgreSQL中的索引

前言 索引是加速搜索引擎检索数据的一种特殊表查询。简单地说&#xff0c;索引是一个指向表中数据的指针。一个数据库中的索引与一本书的索引目录是非常相似的。 拿汉语字典的目录页&#xff08;索引&#xff09;打比方&#xff0c;我们可以按拼音、笔画、偏旁部首等排序的目录…...

windows的批量解锁

场景 场景是我从github上拉了一个c#项目启动的时候报错&#xff0c; 1>C:\Program Files\Microsoft Visual Studio\2022\Community\MSBuild\Current\Bin\amd64\Microsoft.Common.CurrentVersion.targets(3327,5): error MSB3821: 无法处理文件 UI\Forms\frmScriptBuilder.…...

Nginx配置微服务避免actuator暴露

微服务一般在扫漏洞的情况下&#xff0c;需要屏蔽actuator健康检查 # 避免actuator暴露 if ($request_uri ~ "/actuator") { return 403; }...

GEE——在GEE中计算地形位置指数TPI

简介: DEM中的TPI计算是指通过计算每个像元高程与其邻域高程的差值来计算地形位置指数(Topographic Position Index)。TPI 是描述地形起伏度和地形形态的一个重要指标,可以用于地貌分类、土壤侵蚀、植被分布等领域。 地形位置指数(Topographic Position Index,TPI)是用…...

树的基本操作(数据结构)

树的创建 //结构结点 typedef struct Node {int data;struct Node *leftchild;struct Node *rightchild; }*Bitree,BitNode;//初始化树 void Create(Bitree &T) {int d;printf("输入结点(按0为空结点):");scanf("%d",&d);if(d!0){T (Bitree)ma…...

Python复刻游戏《贪吃蛇大作战》

入门教程、案例源码、学习资料、读者群 请访问&#xff1a; python666.cn 大家好&#xff0c;欢迎来到 Crossin的编程教室 &#xff01; 曾经有一款小游戏刷屏微信朋友圈&#xff0c;叫做《贪吃蛇大作战》。一个简单到不行的游戏&#xff0c;也不知道怎么就火了&#xff0c;还上…...

SpringCloud之Gateway整合Sentinel服务降级和限流

1.下载Sentinel.jar可以图形界面配置限流和降级规则 地址:可能需要翻墙 下载jar文件 2.引入maven依赖 <!-- spring cloud gateway整合sentinel的依赖--><dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-alibaba-s…...

深度学习——深度卷积神经网络(AlexNet)

深度学习——深度卷积神经网络&#xff08;AlexNet) 文章目录 前言一、学习表征二、AlexNet实现2.1. 模型设计2.2. 激活函数2.3. 容量控制与预处理2.4. 训练模型 总结 前言 在前面学习了卷积神经网络的基本原理&#xff0c;之后将继续学习现代卷积神经网络架构。而本章将学习其…...

提高编程效率-Vscode实用指南

您是否知道全球73%的开发人员依赖同一个代码编辑器&#xff1f; 是的&#xff0c;2023 年 Stack Overflow 开发者调查结果已出炉&#xff0c;Visual Studio Code 迄今为止再次排名第一最常用的开发环境。 “Visual Studio Code 仍然是所有开发人员的首选 IDE&#xff0c;与专业…...

ES 数据库

ES 数据库 通过 API 查询通过 JSON 查询 熟悉 es 的同学都知道 es 一般有两种查询方式 1&#xff0c;在 java 中构建查询对象&#xff0c;调用 es 提供的 api 做查询 2&#xff0c;使用 json 调用接口做查询 查询语句无非是将足够的信息丢给数据库&#xff0c;但是它却和 SQL …...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

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

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

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...