LeetCode算法心得——使用最小花费爬楼梯(记忆化搜索+dp)

大家好,我是晴天学长,很重要的思想动规思想,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪


1)使用最小花费爬楼梯

在这里插入图片描述

给你一个整数数组 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


2) .算法思路

  • 有点像变了的样子的打家劫舍,可以打劫附近的房子了。

3) .算法步骤

定义一个整型数组 memo 和 cost,用于存储记忆化搜索的结果和每个楼梯的代价。
创建 minCostClimbingStairs 方法来启动算法。在该方法中,初始化 memo 数组和 cost 数组,并将 memo 数组的所有元素初始化为 -1。
调用 dfs 方法,将起始索引设为 cost.length - 1(最后一个楼梯),并返回从最后一个楼梯开始上楼梯的最小代价。
在 dfs 方法中,首先检查是否已经搜索过当前索引 i 的结果。如果在 memo 数组中存在已计算的值,则直接返回该值作为结果,避免重复计算。
如果当前索引 i 小于 0,表示已经超出楼梯范围,返回 0。
否则,根据动态规划的思想,当前楼梯 i 的最小代价等于从前一个楼梯 i-1 或者前两个楼梯 i-2 上来的最小代价加上当前楼梯的代价。使用递归调用 dfs 方法,分别计算从 i-1 楼梯和 i-2 楼梯上来的最小代价,并将它们与当前楼梯的代价相加并取最小值。
将计算得到的结果存储在 memo 数组中,以备后续使用。
返回当前索引 i 的结果作为最终答案,即从最后一个楼梯出发的最小代价。


4).代码示例

方法1:记忆化搜索。
 class Solution {
        int[] memo;
        int[] cost;

        public int minCostClimbingStairs(int[] cost) {
            memo = new int[1000];
            this.cost = cost;
            Arrays.fill(memo, -1);
            return Math.min(dfs(cost.length - 1), dfs(cost.length - 2));
        }

        //变相的打家劫舍, 到楼梯发现已经爬上来了,不能选择不爬
        private int dfs(int i) {
            if (i < 0) return 0;
            if (memo[i] != -1) return memo[i];
            int result = Math.min(dfs(i - 1) + cost[i], dfs(i - 2) + cost[i]);
            memo[i] = result;
            return result;
        }
    }
方法2:动态规划dp
//感兴趣的小伙伴可以用一个数组来打表,优化空间复杂度。
 class Solution {
        public int minCostClimbingStairs(int[] cost) {
            int[] dp = new int[cost.length];
            dp[0] = cost[0];
            dp[1] = cost[1];
            for (int i = 2; i < dp.length; i++) {
                dp[i] = Math.min(dp[i - 1] + cost[i], dp[i - 2] + cost[i]);
            }
            return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
        }
    }

5).总结

  • 状态转移思想。

试题链接:

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

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

相关文章

WinApp自动化测试之工具的选择

WinApp&#xff08;Windows APP&#xff09;是运行在Windows操作系统上的应用程序&#xff0c;通常会提供一个可视的界面&#xff0c;用于和用户交互。 例如运行在Windows系统上的Microsoft Office、PyCharm、Visual Studio Code、Chrome&#xff0c;都属于WinApp。常见的WinA…

【Linux】xfs文件系统的xfs_info命令

xfs_info命令 ① 查看命令工具自身的版本号 xfs_info -V ② 查看指定XFS设备的详细信息 xfs_info <device_name> 其他的一些命令可以使用man xfs_info去查阅man手册&#xff1a;

vue3中v-for报错 ‘item‘ is of type ‘unknown‘

报错 在写vue3ts的项目&#xff0c;得到一个数组&#xff0c;需要循环展示&#xff0c;使用v-for循环&#xff0c;写完之后发现有个报错&#xff0c;如下&#xff1a; 解决 props的时候使用PropType将数据类型完整标注即可 以为没有显示的表示出list中item的类型&#xff…

面对网络渠道低价 品牌如何应对

品牌在发展过程中&#xff0c;会不断拓展自己的销售渠道&#xff0c;网站渠道是顺应消费者习惯的一种销售战场&#xff0c;没有品牌会轻易丢弃这个渠道&#xff0c;但是网络渠道的低价又是很常见的&#xff0c;所以只有及时的治理渠道低价&#xff0c;对应的渠道才会发展越来越…

python数据结构与算法-10_递归

递归 Recursion is a process for solving problems by subdividing a larger problem into smaller cases of the problem itself and then solving the smaller, more trivial parts. 递归是计算机科学里出现非常多的一个概念&#xff0c;有时候用递归解决问题看起来非常简单…

呼叫中心自建好还是云外呼好用?

传统的呼叫中心在科技的发展下已经被不适用了&#xff0c;都开始使用起智能化的呼叫中心&#xff0c;一个是自建式呼叫中心&#xff0c;一个是云外呼系统。那自建式呼叫中心与云外呼系统的区别有哪些呢&#xff1f; 1、企业自建呼叫中心 劣势 系统维护更新难&#xff1a;自建…

Proxifier联动BurpSuite抓取小程序

直接上软件包 Proxifier安装包https://pan.quark.cn/s/7fb9ad6deb7cProxifier配置文件https://pan.quark.cn/s/049c5f21c97e 无话可说直接操作 1、安装Proxifier步骤可以省略..... 2、将下面文件导入到Proxifier中 3、左上角文件-导入配置文件&#xff08;因为我已经导入过…

快来瞧瞧这样制作出来的电子画册,还便于分享宣传呢!

说起电子画册制作&#xff0c;很多人都不知道从何入手。与传统纸质画册相比&#xff0c;电子画册最大的优点是便于传阅&#xff0c;通过微信、QQ等社交平台都能进行转发和分享。而且内容的排版基本上和纸质画册一致&#xff0c;不同的是&#xff0c;无论图片还是文字都可以赋予…

网络渗透测试(wireshark 抓取QQ图片)

1.打开wireshark 这里我用的wifi连接 所以点开wifi就好 打开wifi之后就开始在本机上进行抓包了 我们先给我们的QQ发送一张图片&#xff0c;用自己的手机发送给电脑 然后点击左上角的正方形&#xff0c;停止捕获抓包 QQ的关键词是oicq&#xff0c;所以我们直接找 打开oicq …

2023年国自然植物科学相关面上项目信息公布(小麦、大麦、棉花、大豆、玉米)

2024年申报国自然项目基金撰写及技巧http://mp.weixin.qq.com/s?__bizMzA4NTAwMTY1NA&mid2247575761&idx1&sn32dbacd3393f3b76a1e0668e4b8b3c89&chksm9fdd7c08a8aaf51ec31d4790067bb57751a09947eeb7e728b8c008d26b89adba37e0cab32a62&scene21#wechat_redi…

【23真题】难!下沙“小清华”难度爆增!

今天分享的是23年“下沙小清华”杭州电子科技大学843的信号与系统试题及解析。 本套试卷难度分析&#xff1a;22年杭电843考研真题&#xff0c;我也发布过&#xff0c;若有需要&#xff0c;戳这里自取&#xff01;平均分为112分&#xff0c;最高分为145分&#xff01;该院校23…

requests 库中响应最大文件大小和最大连接超时时间的设定

最近&#xff0c;requests-toolbelt库的开发者jvanasco提出了一项特性请求&#xff0c;即在发送请求时设置响应的最大文件大小和最大连接超时时间。 对于最大连接超时时间的问题&#xff0c;我们可以借鉴requests-toolbelt库的开发者kevinburke的建议&#xff0c;将请求放入线程…

基于变色龙算法优化概率神经网络PNN的分类预测 - 附代码

基于变色龙算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于变色龙算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于变色龙优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神经网络…

我的创作纪念日2048天

机缘 在这特殊的日子里&#xff0c;我要庆祝我的 CSDN 创作纪念日——已经坚持了整整2048天&#xff01; 在这2048天里&#xff0c;我经历了很多成长和收获。作为一名技术写手&#xff0c;我投入了大量的时间和精力来分享我的知识和经验。我曾经写过关于数据库、数据同步、数…

系列四、ThreadLocal的工作原理

一、内存结构图 二、工作原理 &#xff08;1&#xff09;Thread有一个类型为ThreadLocal.ThreadLocalMap threadLocals 的实例变量&#xff0c;即每个线程都有一个属于自己的ThreadLocalMap&#xff1b; &#xff08;2&#xff09;ThreadLocalMap内部维护着Entry数组&#xff0…

leetcode:环形链表

题目描述 题目链接&#xff1a;141. 环形链表 - 力扣&#xff08;LeetCode&#xff09; 题目分析 我们先了解一个知识&#xff1a;循环链表 尾结点不指向NULL&#xff0c;指向头就是循环链表 那么带环链表就意味着尾结点的next可以指向链表的任意一个结点&#xff0c;甚至可…

指令不明,成员困惑,项目经理如何明确每个人的职责

有一个故事&#xff0c;讲述了一个餐厅客人在点餐时要求吃螃蟹&#xff0c;但是餐厅已经卖完了。幸运的是&#xff0c;楼下的商铺有售卖螃蟹。 经理吩咐小李去询问价格&#xff0c;小李迅速返回并汇报了价格。然而&#xff0c;经理进一步询问了螃蟹的数量&#xff0c;小李才意…

Git远程库操作(GitHub)

GitHub 网址&#xff1a;https://github.com/ 创建远程仓库 远程仓库操作 命令名称作用git remote -v查看当前所有远程地址别名git remote add 别名 远程地址起别名git push 别名 分支推送本地分支上的内容到远程仓库git clone 远程地址将远程仓库的内容克隆到本地git pull 别…

关于CRM系统中的客户,您需要知道这些

今天为大家讲解CRM中客户是什么&#xff1f;如何进行客户管理&#xff1f;CRM系统中有购买意向和已经购买了产品的消费者都属于客户。对于B2B企业&#xff0c;会将企业看作客户&#xff0c;而对于B2C企业来说每一位消费的个体都是客户。 CRM中的客户管理无疑是业务重点&#x…

计算机毕业设计项目选题推荐(免费领源码)java+springboot+mysql社区团购APP 02043

目录 摘要 1 绪论 1.1 研究背景 1.2国内外研究现状 1.3本课题主要工作 1.4论文结构与章节安排 2 社区团购系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.…