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

本文主要是介绍代码随想录算法训练营第三十八天| 动态规划理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 动态规划理论基础
  • 1.斐波那契数
  • 2.爬楼梯
  • 3.使用最小花费爬楼梯


动态规划理论基础

动态规划(Dynamic Programming),动态规划中每一个状态一定是由上一个状态推导出来的。
动态规划的解题步骤:

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

动态规划应该如何debug:找问题的最好方式就是把dp数组打印出来,看看究竟是不是按照自己思路推导

1.斐波那契数

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

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

给定 n,请计算 F(n)

示例 1:

  • 输入:n = 2
  • 输出:1
  • 解释:F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2:

  • 输入:n = 3
  • 输出:2
  • 解释:F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3:

  • 输入:n = 4
  • 输出:3
  • 解释:F(4) = F(3) + F(2) = 2 + 1 = 3

提示:

  • 0 <= n <= 30

题目比较简单,主要用来加深动归解题方法理解
动规五部曲:

  1. 确定dp数组以及下标的含义,dp[i]的定义为:第i个数的斐波那契数值是dp[i]
  2. 确定递推公式:dp[i] = dp[i - 1] + dp[i - 2];
  3. dp数组如何初始化dp[0] = 0;dp[1] = 1;
  4. 确定遍历顺序:dp[i]是依赖 dp[i - 1] 和 dp[i - 2],所以是从前到后遍历
  5. 举例推导dp数组:0 1 1 2 3 5 8 13 21 34 55

代码如下

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];}
};

时间复杂度:O(n)
空间复杂度:O(1)

2.爬楼梯

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

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

示例 1:

  • 输入:n = 2
  • 输出:2
  • 解释:有两种方法可以爬到楼顶。
      1. 1 阶 + 1 阶
      1. 2 阶

示例 2:

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

提示:

  • 1 <= n <= 45

第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来,那么就可以想到动态规划了
动规五部曲:

  1. dp数组以及下标的含义:dp[i]: 爬到第i层楼梯,有dp[i]种方法
  2. 递推公式:dp[i] = dp[i - 1] + dp[i - 2] 。
  3. dp数组初始化:dp[1] = 1,dp[2] = 2
  4. 遍历顺序:从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序是从前向后遍历
  5. 举例推导dp数组:1 2 3 5 8 (i = 1 2 3 4 5)
class Solution {
public:int climbStairs(int n) {if(n <= 1) return n;int dp[2];dp[0] = 1;dp[1] = 2;for (int i = 3; i <= n; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

时间复杂度:O(n)
空间复杂度:O(1)

3.使用最小花费爬楼梯

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

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

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

示例 1:

  • 输入:cost = [10,15,20]
  • 输出:15
  • 解释:你将从下标为 1 的台阶开始。
    • 支付 15,向上爬两个台阶,到达楼梯顶部。
      总花费为 15。

示例 2:

  • 输入:cost = [1,100,1,1,1,100,1,1,100,1]
  • 输出:6
  • 解释:你将从下标为 0 的台阶开始。
    • 支付 1,向上爬两个台阶,到达下标为 2 的台阶。
    • 支付 1,向上爬两个台阶,到达下标为 4 的台阶。
    • 支付 1,向上爬两个台阶,到达下标为 6 的台阶。
    • 支付 1,向上爬一个台阶,到达下标为 7 的台阶。
    • 支付 1,向上爬两个台阶,到达下标为 9 的台阶。
    • 支付 1,向上爬一个台阶,到达楼梯顶部。
      总花费为 6。

提示:

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

动规五部曲:

  1. dp数组以及下标的含义:dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]
  2. 递推公式:
    可以有两个途径得到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]
  3. dp数组初始化:dp[0] = 0,dp[1] = 0;
  4. 遍历顺序:从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序是从前向后遍历
  5. 举例推导dp数组:

在这里插入图片描述

代码如下

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0;dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.size()];}
};

时间复杂度:O(n)
空间复杂度:O(n)

因为dp[i]就是由前两位推出来的,所以只维护dp[0]和dp[1]空间复杂度也可为O(1)

这篇关于代码随想录算法训练营第三十八天| 动态规划理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/783605

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚