代码随想录算法训练营第三十八天|动态规划|理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

news/2024/4/13 10:45:15/文章来源:https://blog.csdn.net/princess_FU/article/details/136546797

理论基础

文章
说实话,没做过题连理论基础都看不懂
1 确定dp数组(dp table)以及下标的含义
2 确定递推公式
3 dp数组如何初始化
4 确定遍历顺序
5 举例推导dp数组

这道题目我举例推导状态转移公式了么?
我打印dp数组的日志了么?
打印出来了dp数组和我想的一样么?

509. 斐波那契数

文章

斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你n ,请计算 F(n) 。

示例 1:

输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:

输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:

输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3
提示:

0 <= n <= 30

题目简单,用于理解动态规划

class Solution {
public:int fib(int N) {if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

当然可以用递归的方法

70. 爬楼梯

文章

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

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

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

想不出来啊
到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来,那么就可以想到动态规划了。
dp[i]: 爬到第i层楼梯,有dp[i]种方法


class Solution {
public:int climbStairs(int n) {if (n <= 1) return n;int dp[3];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {int sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
};

746. 使用最小花费爬楼梯

文章讲解
数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。

每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1:

输入:cost = [10, 15, 20]
输出:15
解释:最低花费是从 cost[1] 开始,然后走两步即可到阶梯顶,一共花费 15 。
示例 2:

输入:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出:6
解释:最低花费方式是从 cost[0] 开始,逐个经过那些 1 ,跳过 cost[3] ,一共花费 6 。
提示:

cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据,范围为 [0, 999]

能想到由前两步推,但是没太象具体,不打算走非min的步了,其实不对。
还是要按照步骤来
min(dp1 + cost[i - 1], dp0 + cost[i - 2])

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int dp0 = 0;int dp1 = 0;for (int i = 2; i <= cost.size(); i++) {int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);dp0 = dp1; // 记录一下前两位dp1 = dpi;}return dp1;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【管理咨询宝藏资料36】某知名咨询公司战略规划内部培训

【管理咨询宝藏资料36】某知名咨询公司战略规划内部培训 【关键词】战略规划、内部培训、管理咨询 【文件核心观点】 - 战略明晰框架思路&#xff1a;一棵大树五只苹果&#xff0c;通过战略定位图的核心性、层次性和浓缩性来保障战略明晰的有效性、直观性和可实施性。 - 企业战…

python统计分析——泊松回归

参考资料&#xff1a;用python动手学统计学 概率分布为泊松分布、联系函数为对数函数的广义线性模型叫作泊松回归。解释变量可以有多个&#xff0c;连续型和分类型的解释变量也可以同时存在。 1、案例说明 分析不同气温与啤酒销量的关系。构造不同气温下的销量的数学模型&…

SpringMVC的工作流程简介

SpringMVC控制器工作流程 用户通过浏览器向服务器发送请求&#xff0c;请求会被Spring MVC的前端控制器DispatcherServlet所拦截; DispatcherServlet拦截到请求后&#xff0c;会调用HandlerMapping处理器映射器; 处理器映射器根据请求URL找到具体的处理器&#xff0c;生成处理…

Transformer中的FlashAttention

FlashAttention是一种用于Transformer模型的近似注意力机制&#xff0c;旨在减少注意力计算和内存需求。引入FlashAttention是因为传统Transformer模型中的自注意力机制在处理长序列时存在时间和存储复杂度上的挑战&#xff0c;需要大量的计算资源和内存来处理更长的上下文背景…

排序算法:插入排序和希尔排序

一、插入排序 1.基本原理 插入排序&#xff08;英语&#xff1a;Insertion Sort&#xff09;是一种简单直观的排序算法。它的工作原理是通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置并插入。插入排序在实现上…

运维知识点-JBoss

JBoss 介绍介绍 JBoss是一个基于J2EE的开放源代码的应用服务器,也是一个运行EJB(Enterprise JavaBean)的容器和服务器。它支持EJB 1.1、EJB 2.0和EJB3的规范,体现了J2EE规范中最新的技术。JBoss遵循LGPL许可,可以在任何商业应用中免费使用,并且由开源社区开发,这使得JB…

ARM64汇编04 - 条件码

关于分支控制与条件码的作用可以去看 《CSAPP》的第 3.6 节&#xff0c;讲的非常清楚&#xff0c;建议看看&#xff0c;这里就不重复了。 我们直接使用一个例子来简单理解汇编是如何实现分支控制的&#xff1a; #include <stdio.h> #include <stdlib.h> #include…

软件测试相关概念和bug的相关总结

文章目录 什么是测试什么是需求测试用例(CASE)什么是BUG软件的生命周期开发模型瀑布模型螺旋模型增量模型和迭代模型 敏捷测试模型v模型W模型(双V模型) 软件测试的生命周期如何描述一个bugbug的级别bug的生命周期.产生争执怎么办 什么是测试 测试是测试人员用来检验软件的实际运…

面试题之——事务失效的八大情况

事务失效的八大情况 一、非public修饰的方法 Transactional注解只能在在public修饰的方法下使用。 /*** 私有方法上的注解&#xff0c;不生效&#xff08;因私有方法Spring扫描不到该方法&#xff0c;所以无法生成代理&#xff09;*/ Transactional private boolean test() …

python爬虫(2)

继上节 查看数组维数 可以使用数组的ndim属性 代码示例如下&#xff1a; import numpy as np c np.random.randint(1,9,5) print(c.ndim) 结果如下&#xff1a; 当然这些也可以结合前面的各种用法来使用 1、选取数组元素 &#xff08;1&#xff09;一维数组的元素…

ClickHouse SQL Reference (四)数据类型

Tuple(T1, T2, …) 元素元组&#xff0c;每个元素都有一个单独的类型。元组必须至少包含一个元素。 元组用于临时列分组。在查询中使用IN表达式时&#xff0c;以及指定lambda函数的某些形式参数时&#xff0c;可以对列进行分组。有关更多信息&#xff0c;请参阅IN操作符和高阶…

css 用flex做成田字型

哈喽&#xff0c;各位小伙伴&#xff01;今天给大家来css控制div完成田字型样式&#xff0c;来&#xff0c;看看下面的效果图&#xff1a; 一看就知道你们想要代码了&#xff0c;不急。代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head>&…

Spring Boot 生成与解析Jwt

Spring Boot 生成与解析Jwt Maven依赖 <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.9.1</version> </dependency>生成&解析 package yang;import io.jsonwebtoken.Claims…

黑马java-JavaSE进阶-网络编程

1.网络编程 可以让设备中的程序与网络上其他设备中的程序进行数据交互&#xff08;实现网络通信&#xff09; 2.基本通信架构 基本通信架构有两种形式&#xff1a;CS架构、BS架构 3.基本概念&#xff1a; IP&#xff1a;设备在网络中的地址&#xff0c;是唯一的标识 端口&#…

学c++对Python有帮助吗?

学习C对Python编程确实有帮助&#xff0c;尽管这两种语言在许多方面有很大的不同。以下是学习C可能对Python编程产生帮助的几个方面&#xff1a; 理解底层概念&#xff1a;C是一种更接近硬件的编程语言&#xff0c;它要求程序员更深入地理解内存管理、指针、数据类型等底层概念…

【Proteus仿真】【51单片机】坐姿矫正提醒器设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真51单片机控制器&#xff0c;使用LCD1602液晶显示模块、HC-SR04超声波模块、蜂鸣器、按键、人体红外传感器等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显示超声波检…

Android fragment的使用案例

效果图&#xff1a;两个点击事件&#xff0c;显示不同的fragment布局 默认是如下图&#xff0c;点击页面一也如下图 点击页面二如下图&#xff1a; Android Fragment的生命周期是与其所在的Activity紧密相关的。当一个Fragment被添加到Activity中时&#xff0c;它将经历一系列…

Android使用WebView打开网页链接(内嵌H5网页)的两种方式之一

发布Android应用&#xff0c;除了用原生开发外&#xff0c;更多是采用内嵌H5网页的方式来做&#xff0c;便于更新以及多平台使用。 一、第一种方式是直接通过WebView打开外部H5链接。 新建Android工程 直接创建一个工程&#xff0c;点击运行就可以了&#xff0c;打开是个空页…

大路灯护眼灯哪个牌子好?精心挑选五款大路灯,无广分享

当前&#xff0c;大路灯作为一种良好帮助改善光线环境的工具&#xff0c;受到了广泛关注&#xff0c;并以其卓越的光线舒适度功能赢得了许多用户的青睐。然而&#xff0c;其迅速增长的人气也伴随着一些负面反响&#xff0c;其中包括了关于可能对眼睛造成损伤和健康风险的报道。…

代码之旅:我的算法探索之路(二)力扣 最接近的三数之和

目录 LeetCode 第16题 最接近的三数之和 题目 解题思路 代码 结果 LeetCode 第18题 四数之和 题目 解题思路 代码 结果 LeetCode 第16题 最接近的三数之和 题目 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数&#xff0c;使…