镇江市建设工程安全监督站网站,html5静态网页设计,湛江做网站咨询电话,桂林网红民宿#x1f388;算法那些事专栏说明#xff1a;这是一个记录刷题日常的专栏#xff0c;每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目#xff0c;在这立下Flag#x1f6a9; #x1f3e0;个人主页#xff1a;Jammingpro #x1f4d5;专栏链接… 算法那些事专栏说明这是一个记录刷题日常的专栏每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目在这立下Flag 个人主页Jammingpro 专栏链接算法那些事 每日学习一点点技术累计看得见 题目
题目描述
给你一个整数数组 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
题解
由题目可知如果想爬到第n个台阶可以从n-1号台阶爬1个台阶到达也可以从n-2号台阶爬2个台阶到达。我们只要求出这两个台阶的花费从中选择小的那个就可以得到爬到第n个台阶的花费即sumCost[n]min{sumCost[n-1], sumCost[n-2]} cost[n]。
以示例1为例爬到下标为0的台阶的花费为10即从开始的地方爬到第1号台阶到达因而sumCost[0]10爬到下标为1的台阶的花费为15即从开始的地方爬2个台阶到达或从0号台阶爬1个台阶到达因而sumCost[1]min{sumCost[0], 0}cost[1]01515爬到下标为2的她姐的花费为30因为sumCost[2]min{sumCost[1], sumCost[0]}cost[2]102030爬到楼梯顶部的花费min{sumCost[2], sumCost[1]}15。
通过上面的分析我们得到了状态转移方程也叫做递推公式那么我们就可以开始编码了↓↓↓
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorintdp(n);dp[0] cost[0];dp[1] cost[1];for(int i 2; i n; i)dp[i] min(dp[i - 1], dp[i - 2]) cost[i];return min(dp[n - 1], dp[n - 2]);}
};这种解法的时空复杂度均为O(N)可以通过滚动数组的方式将其空间复杂度将为O(1)。我们设置3个变量cur、pre、ppre分别保存当前台阶花费和前两个台阶的花费。
psppre初始化为cost[0]pre初始化为cost[1]cur初始化为min{cosy[0], cost[1]} cost[2]这3步初始化求出了0号、1号、2号台阶的最小花费。通过pprepre和precur操作后ppre、pre分别保存的是第1号和第2号台阶的最小花费通过curmin(ppre,pre)cost[3]可计算出第3号台阶的最小花费。以此类推…
代码实现如下↓↓↓
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();if(n 2) return min(cost[0], cost[1]);int ppre cost[0], pre cost[1], cur min(cost[0], cost[1]) cost[2];for(int i 3; i n; i){ppre pre;pre cur;cur min(ppre, pre) cost[i];}return min(pre, cur);}
};本文存在不足欢迎留言或私信批评、指正。希望我的解决方法能够对你有所帮助~~ 今日打卡完成点亮小星星☆→★
