746. 使用最小花费爬楼梯
2022/2/28 23:26:28
本文主要是介绍746. 使用最小花费爬楼梯,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
746. 使用最小花费爬楼梯
题目链接:746. 使用最小花费爬楼梯(简单)
给你一个整数数组 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
解题思路
该题可用动态规划来解。
-
确定dp数组以及其下标的含义
dp[i]
表示为从第i
层台阶向上爬(无论是一步还是两步)所需(总)花费的最少体力 -
确定递推公式
对某个第
i
阶来说,可以是从第i-1
阶爬上来,也可以是从第i-2
阶爬上来。通过取第i-1
阶和第i-2
阶中花费的最小体力,才能使得第i
阶花费的体力更小。也就是说dp[i]
取决于dp[i-1]
和dp[i-2]
两者的最小值。递推公式为:dp[i] = min(dp[i - 1], dp [i - 2]) + cost[i]
-
dp数组的初始化
dp[0] = cost[0],dp[1] = cost[1]
-
确定遍历顺序
从前向后
-
举例推导dp数组(下标从0开始)
当
cost = [1,100,1,1,1,100,1,1,100,1]
时,dp =[1,100,2,3,3,103,4,5,104,6]
C++
int minCostClimbingStairs(vector<int>& cost) { // dp[i]定义为:从第i层台阶向上爬(无论是一步还是两步)所需(总)花费的最少体力 vector<int> dp(cost.size()); dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < cost.size(); i++) { dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]; } //到达顶层时不需要再往上爬了,所以可以理解为此层消耗的体力为0,所以直接取倒数第一步、第二步的最小值 return dp[cost.size() - 1] > dp[cost.size() - 2] ? dp[cost.size() - 2] : dp[cost.size() - 1]; }
JavaScript
/** * @param {number[]} cost * @return {number} */ var minCostClimbingStairs = function(cost) { let dp = new Array(cost.length); dp[0] = cost[0]; dp[1] = cost[1]; for (let i = 2; i < cost.length; i++) { dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; } return Math.min(dp[cost.length - 1], dp[cost.length - 2]); };
时间复杂度:O(N)
空间复杂度:O(N)
这篇关于746. 使用最小花费爬楼梯的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?