当前位置: 首页 > 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 …...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...