代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

一、斐波那契数

相关题目:Leetcode509
文档讲解:Leetcode509
视频讲解:Leetcode509

1. Leetcode509. 斐波那契数

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

  • F(0) = 0,F(1) = 1
  • F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n) 。

  • 思路:

    • 动态规划五部曲
      • 确定 dp 数组以及下标的含义:第 i 个数的斐波那契数值是 dp[i]
      • 确定递推公式:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
      • dp 数组如何初始化:dp[0] = 0;dp[1] = 1
      • 确定遍历顺序:从递归公式可以看出,dp[i] 是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历
      • 举例推导 dp 数组:当 N 为10的时候,dp 数组应该是如下的数列:0 1 1 2 3 5 8 13 21 34 55,如果代码写出来,发现结果不对,就把 dp 数组打印出来看看和我们推导的数列是不是一致的
  • 动态规划

##动态规划(版本一)
class Solution:def fib(self, n: int) -> int:# 排除 Corner Caseif n == 0:return 0# 创建 dp table dp = [0] * (n + 1)# 初始化 dp 数组dp[0] = 0dp[1] = 1# 遍历顺序: 由前向后。因为后面要用到前面的状态for i in range(2, n + 1):# 确定递归公式/状态转移公式dp[i] = dp[i - 1] + dp[i - 2]# 返回答案return dp[n]##动态规划(版本二)
class Solution:def fib(self, n: int) -> int:if n <= 1:return ndp = [0, 1]for i in range(2, n + 1):total = dp[0] + dp[1]dp[0] = dp[1]dp[1] = totalreturn dp[1]##动态规划(版本三)
class Solution:def fib(self, n: int) -> int:if n <= 1:return nprev1, prev2 = 0, 1for _ in range(2, n + 1):curr = prev1 + prev2prev1, prev2 = prev2, currreturn prev2
  • 递归
class Solution:def fib(self, n: int) -> int:if n < 2:return nreturn self.fib(n - 1) + self.fib(n - 2)

二、爬楼梯

相关题目:Leetcode70
文档讲解:Leetcode70
视频讲解:Leetcode70

1. Leetcode70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数

  • 思路:

    • 动规五部曲
      • 确定 dp 数组以及下标的含义:爬到第 i 层楼梯,有 dp[i] 种方法。

      • 确定递推公式:从 dp[i] 的定义可以看出 dp[i] 可以由两个方向推出来:

        • 上 i-1 层楼梯,有 dp[i - 1] 种方法,再一步跳一个台阶就是 dp[i] 了。
        • 上 i-2 层楼梯,有 dp[i - 2] 种方法,再一步跳两个台阶就是 dp[i] 了。

        所以 dp[i] 就是 dp[i - 1] 与 dp[i - 2] 之和!

      • dp 数组如何初始化:当 i 为0,dp[i] 应该是多少呢,注意到题目中说了 n 是一个正整数,题目根本就没说 n 有为0的情况,所以本题其实就不应该讨论 dp[0] 的初始化!不考虑 dp[0] 如何初始化,只初始化 dp[1] = 1,dp[2] = 2,然后从 i = 3 开始递推,这样才符合 dp[i] 的定义。

      • 确定遍历顺序:从递推公式 dp[i] = dp[i - 1] + dp[i - 2] 中可以看出,遍历顺序一定是从前向后遍历的。

      • 举例推导dp数组:当 n 为5的时候,dp 数组应该是这样的:
        请添加图片描述

    • 拓展:若每次可以爬 1,2,…,m 个台阶,有多少种方法爬到 n 阶楼顶。思路类似本题,题目见 卡码网57.爬楼梯。
  • 动态规划

##动态规划(版本一)
# 空间复杂度为O(n)版本
class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return ndp = [0] * (n + 1)dp[1] = 1dp[2] = 2for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]##动态规划(版本二)
# 空间复杂度为O(3)版本
class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return ndp = [0] * 3dp[1] = 1dp[2] = 2for i in range(3, n + 1):total = dp[1] + dp[2]dp[1] = dp[2]dp[2] = totalreturn dp[2]##动态规划(版本三)
# 空间复杂度为O(1)版本
class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return nprev1 = 1prev2 = 2for i in range(3, n + 1):total = prev1 + prev2prev1 = prev2prev2 = totalreturn prev2

三、使用最小花费爬楼梯

相关题目:Leetcode746
文档讲解:Leetcode746
视频讲解:Leetcode746

1. Leetcode746. 使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
提示:

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

    • 动规五部曲
      • 确定 dp 数组以及下标的含义:dp[i] 的定义为到达第 i 台阶所花费的最少体力为 dp[i]。

      • 确定递推公式:可以有两个途径得到 dp[i],一个是 dp[i-1] 一个是 dp[i-2]:

        • dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
        • dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

        为了所费体力最小,选择从 dp[i - 1] 和 dp[i - 2] 跳至 dp[i] 耗费少的,即 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。

      • dp 数组如何初始化:由递归公式,只初始化 dp[0] 和 dp[1] 就够了,其他的最终都是 dp[0] 与 dp[1] 推出。题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说到达第0个台阶是不花费的,但从第0个台阶 往上跳的话,需要花费 cost[0]。所以初始化 dp[0] = 0,dp[1] = 0。

      • 确定遍历顺序:因为是模拟台阶,而且 dp[i] 由 dp[i-1] 与 dp[i-2] 推出,所以是从前到后遍历 cost 数组就可以了。

      • 举例推导 dp 数组:例:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,模拟一下 dp 数组的状态变化,如下:
        请添加图片描述

  • 动态规划

##动态规划(版本一)
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0] * (len(cost) + 1)dp[0] = 0  # 初始值,表示从起点开始不需要花费体力dp[1] = 0  # 初始值,表示经过第一步不需要花费体力for i in range(2, len(cost) + 1):# 在第i步,可以选择从前一步(i-1)花费体力到达当前步,或者从前两步(i-2)花费体力到达当前步# 选择其中花费体力较小的路径,加上当前步的花费,更新dp数组dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])return dp[len(cost)]  # 返回到达楼顶的最小花费##动态规划(版本二)
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp0 = 0  # 初始值,表示从起点开始不需要花费体力dp1 = 0  # 初始值,表示经过第一步不需要花费体力for i in range(2, len(cost) + 1):# 在第i步,可以选择从前一步(i-1)花费体力到达当前步,或者从前两步(i-2)花费体力到达当前步# 选择其中花费体力较小的路径,加上当前步的花费,得到当前步的最小花费dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2])dp0 = dp1  # 更新dp0为前一步的值,即上一次循环中的dp1dp1 = dpi  # 更新dp1为当前步的最小花费return dp1  # 返回到达楼顶的最小花费##动态规划(版本三)
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0] * len(cost)dp[0] = cost[0]  # 第一步有花费dp[1] = cost[1]for i in range(2, len(cost)):dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]# 注意最后一步可以理解为不用花费,所以取倒数第一步,第二步的最少值return min(dp[-1], dp[-2])##动态规划(版本四)
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost)prev_1 = cost[0]  # 前一步的最小花费prev_2 = cost[1]  # 前两步的最小花费for i in range(2, n):current = min(prev_1, prev_2) + cost[i]  # 当前位置的最小花费prev_1, prev_2 = prev_2, current  # 更新前一步和前两步的最小花费return min(prev_1, prev_2)  # 最后一步可以理解为不用花费,取倒数第一步和第二步的最少值

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

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

相关文章

CAD导入arcgis中保持面积不变的方法

1、加载CAD数据&#xff0c;选择面数据&#xff0c;如下&#xff1a; 2、加载进来后&#xff0c;右键导出数据&#xff0c;导出成面shp数据&#xff0c;如下&#xff1a; 3、选择存储路径&#xff0c;导出面后计算面积&#xff0c;如下&#xff1a; 4、与CAD中的闭合线面积核对…

备赛蓝桥杯-Python-考前突击

额&#xff0c;&#xff0c;离蓝桥杯开赛还有十个小时&#xff0c;最近因为考研复习节奏的问题&#xff0c;把蓝桥杯的优先级后置了&#xff0c;突然才想起来还有一个蓝桥杯呢。。 到目前为止python基本语法熟练了&#xff0c;再补充一些常用函数供明天考前再背背&#xff0c;算…

Matlab 汽车ABS的bangbang控制和模糊PID控制

1、内容简介 Matlab 197-汽车ABS的bangbang控制和模糊PID控制 可以交流、咨询、答疑 2、内容说明 略 摘要&#xff1a;本文旨在设计一种利用模糊控制理论优化的pid控制器&#xff0c;控制abs系统&#xff0c;达到对滑移率最佳控制范围的要求 &#xff0c;所提出的方案采用级联…

题目 2701: 蓝桥杯2022年第十三届决赛真题-取模(C/C++/Java组)

题目 2701: 蓝桥杯2022年第十三届决赛真题-取模&#xff08;C/C/Java组&#xff09; 时间限制: 3s 内存限制: 512MB 提交: 6633 解决: 1263 题目描述 给定 n, m &#xff0c;问是否存在两个不同的数 x, y 使得 1 ≤ x < y ≤ m 且 n mod x n mod y 。 输入格式 输入包含多…

蓝桥杯C/C++省赛/国赛注意事项及运行环境配置

大佬的蓝桥杯考前急救指南 对拍&#xff08;手动生成测试数据&#xff09;代码&#xff1a; #include <bits/stdc.h> // 包含所有标准库的头文件 using namespace std; // 使用标准命名空间int main() {srand(time(0)); // 设置随机数种子为当前时间&#xff0c;确保每次…

13、nRF52xx蓝牙学习(GPIOTE组件方式的任务配置)

下面再来探讨下驱动库如何实现任务的配置&#xff0c;驱动库的实现步骤应该和寄存器方式对应&#xff0c;关 键点就是如何调用驱动库的函数。 本例里同样的对比寄存器方式编写两路的 GPOITE 任务输出&#xff0c;一路配置为输出翻转&#xff0c;一路设 置为输出低电平。和 …

使用Apache POI(Java)创建docx文档和表格

1、引入poi 依赖组件 <dependency><groupId>org.apache.poi</groupId><artifactId>poi-scratchpad</artifactId><version>4.0.0</version> </dependency> <dependency><groupId>org.apache.poi</groupId>&…

利用 RNN 预测股票价格:从数据处理到可视化实战

在金融领域&#xff0c;预测股票价格走势一直是众多投资者和研究者关注的焦点。今天&#xff0c;我们将利用深度学习中的循环神经网络&#xff08;RNN&#xff09;来构建一个简单的股票价格预测模型&#xff0c;并详细介绍从数据加载、预处理、模型搭建、训练到最终结果可视化的…

华为RH2288H V3服务器极速重装:从RedHat到openEuler 24超详细重装指南

1 登录iBMC口 2 配置启动项 点击&#xff1a;配置&#xff0c;点击&#xff1a;系统启动项 点击&#xff1a;单次有效&#xff0c;选择&#xff1a;光驱&#xff0c;点击&#xff1a;保存 3 进Remote Contro 点击&#xff1a;远程控制&#xff0c;进入如下界面 点击&#xff1…

+++++背到厌倦。持续更新

Spring IoC 的工作流程: 读取 BeanDefinition: Spring 容器启动时&#xff0c;会读取 Bean 的配置信息 (例如 XML 配置文件、注解或 Java 代码)&#xff0c;并将这些配置信息转换为 BeanDefinition 对象。创建 Bean 实例: 根据 BeanDefinition 中的信息&#xff0c;Spring 容器…

【机器学习算法】基于python商品销量数据分析大屏可视化预测系统(完整系统源码+数据库+开发笔记+详细启动教程)✅

目录 一、项目背景 二、技术思路 三、算法介绍 四、项目创新点 五、开发技术介绍 六、项目展示 一、项目背景 本项目基于Python技术栈构建了"商品销量数据分析与预测系统"&#xff0c;通过自动化爬取淘宝商品多维数据&#xff08;价格、销量、评价、品类等&a…

Server-Sent Events一种允许服务器向客户端发送实时更新的 Web API

Server-Sent Events&#xff08;SSE&#xff09;是一种允许服务器向客户端发送实时更新的 Web API。它基于 HTTP 协议&#xff0c;提供了一种单向的、服务器到客户端的通信机制&#xff0c;客户端可以通过监听服务器发送的事件来接收实时数据。下面从原理、使用场景、代码示例等…