给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
【算法|746. 使用最小花费爬楼梯】示例 1:这题是个dp问题,类似普通爬楼梯,不过加了一个体力,就需要比较最值;
输入:cost = [10,15,20] 输出:15 解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。 总花费为 15 。
dp数组含义:达到此位置的最小体力;
数组初始化:第0阶和第1阶直接花费的体力;
遍历顺序:从前往后;
递推公式:dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
这道题设置的有问题,看似是花费体力去爬,其实只要到达这一层就需要花费cost【i】,并且倒数第二层直接到最后一层不消耗体力,就只能这么写了;
public int minCostClimbingStairs(int[] cost) {
if(cost==null||cost.length==0){
return 0;
}
if(cost.length==1){
return cost[0];
}
int[] dp=new int[cost.length];
dp[0]=cost[0];
dp[1]=cost[1];
//初始化
for (int 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]);
}
推荐阅读
- OJ|阶乘分解 kkmd66
- PTA|本题要求编写程序,以hh:mm:ss的格式输出某给定时间再过n秒后的时间值(超过23:59:59就从0点开始计时)。
- 链表|链表的OJ题练习
- LeetCode编程题解法汇总|力扣解法汇总2038- 如果相邻两个颜色均相同则删除当前颜色
- 算法|常用的快速排序
- 蓝桥杯|acwing 1113. 红与黑(蓝桥杯)
- 强化学习|强化学习笔记(七)演员-评论家算法(Actor-Critic Algorithms)及Pytorch实现
- Python学习笔记|Newton法求解非线性方程(Python实现)
- LeetCode编程题解法汇总|力扣解法汇总393- UTF-8