算法训练(leetcode)二刷第二十八天 | 509. 斐波那契数、70. 爬楼梯、*746. 使用最小花费爬楼梯

devtools/2024/11/17 16:06:57/

刷题记录

  • 509. 斐波那契数
  • 70. 爬楼梯
  • *746. 使用最小花费爬楼梯
    • 动态规划
    • 优化空间复杂度

509. 斐波那契数

leetcode题目地址

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

// java
class Solution {public int fib(int n) {if(n<2) return n;int a = 0, b = 1, c = 0;for(int i=2; i<=n; i++){c = a + b;a = b;b = c;}return c;}
}

70. 爬楼梯

leetcode题目地址

依旧是斐波那契序列问题。

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

// java
class Solution {public int climbStairs(int n) {if(n<=3) return n;int a = 2, b = 3, c = 0;for(int i=4; i<=n; i++){c = a + b;a = b;b = c;}return c;}
}

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

leetcode题目地址

动态规划

动态规划。每一步可以走一个台阶或两个台阶,因此,dp[i]记录到达第i个位置时所花费的开销,

  • 走一阶台阶到达dp[i]:dp[i] = dp[i-1] + cost[i-1]
  • 走两阶台阶到达dp[i]:dp[i] = dp[i-2] + cost[i-2]

因此,得到状态转移方程:
d p [ i ] = m i n ( d p [ i − 1 ] + c o s t [ i − 1 ] , d p [ i − 2 ] + c o s t [ i − 2 ] ) dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) dp[i]=min(dp[i1]+cost[i1],dp[i2]+cost[i2])

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

// java
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length+1];for(int i=2; i<=cost.length; i++){dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);}return dp[cost.length];}
}

优化空间复杂度

每一步的更新以来前两步的结果,因此只需要保留前两步即可。

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

// java
class Solution {public int minCostClimbingStairs(int[] cost) {// int[] dp = new int[cost.length+1];int dp0 = 0, dp1 = 0;for(int i=2; i<=cost.length; i++){int dpi = Math.min(dp1 + cost[i-1], dp0 + cost[i-2]);dp0 = dp1;dp1 = dpi;}return dp1;}
}

http://www.ppmy.cn/devtools/134730.html

相关文章

米家电动牙刷拆解学习

米家声波扫振电动牙刷&#xff1a; 工作电压&#xff1a;3.7V ; 学习下面的执行标准&#xff1a; H桥也有合封的芯片&#xff1a; 用于驱动声波电机的驱动器来自Silergy矽力杰&#xff0c;丝印Ee&#xff0c;型号SY6702&#xff0c;是一颗H桥马达驱动芯片&#xff0c;用…

netcore Kafka

一、新建项目KafakDemo <ItemGroup><PackageReference Include"Confluent.Kafka" Version"2.6.0" /></ItemGroup> 二、Program.cs using Confluent.Kafka; using System; using System.Threading; using System.Threading.Tasks;names…

计算机毕业设计Hadoop+Spark高考推荐系统 高考分数线预测 知识图谱 高考数据分析可视化 高考大数据 大数据毕业设计 Hadoop 深度学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

【视频讲解】Python深度神经网络DNNs-K-Means(K-均值)聚类方法在MNIST等数据可视化对比分析...

全文链接&#xff1a;https://tecdat.cn/?p38289 分析师&#xff1a;Cucu Sun 近年来&#xff0c;由于诸如自动编码器等深度神经网络&#xff08;DNN&#xff09;的高表示能力&#xff0c;深度聚类方法发展迅速。其核心思想是表示学习和聚类可以相互促进&#xff1a;好的表示会…

UniApp 应用、页面与组件的生命周期详解

UniApp 应用、页面与组件的生命周期详解 在uni-app中包含了 应用生命周期、页面生命周期、和组件生命周期&#xff08; Vue.js的&#xff09;函数。 应用生命周期 应用生命周期仅可在App.vue中监听&#xff0c;在其它页面监听无效。 <script>export default {onLaunc…

vue2项目中在线预览csv文件

简介 希望在项目中&#xff0c;在线预览.csv文件&#xff0c;本以为插件很多&#xff0c;结果都只是支持excel&#xff08;.xls、.xlsx&#xff09;一到.csv就歇菜。。。 关于文件预览 vue-office&#xff1a;文档、 查看在线演示demo&#xff0c;支持docx、.xlsx、pdf、ppt…

游戏引擎学习第13天

视频参考:https://www.bilibili.com/video/BV1QQUaYMEEz/ 改代码的地方尽量一张图说清楚吧,懒得浪费时间 game.h #pragma once #include <cmath> #include <cstdint> #include <malloc.h>#define internal static // 用于定义内翻译单元内部函数 #…

SQL 语句优化及编程方法

DBMS生成的执行计划在很大程度上要受到代码外部结构的影响。因此要想优化查询性能&#xff0c;就必须要知道如何写代码才能使优化器的执行效率更高。 但是&#xff0c;不能为了“效率”牺牲代码的可读性&#xff0c;要让代码清晰。 1 查询优化 在解决SQL造成的性能问题时&am…