珠海门户网站建设,做网站的人叫什么软件,做动态效果的插件网站,wordpress微信公众号登录界面题目链接#xff1a;746. 使用最小花费爬楼梯
题目描述
给你一个整数数组 cost #xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用#xff0c;即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 …题目链接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 10000 cost[i] 999
文章讲解代码随想录
视频讲解动态规划开更了| LeetCode746. 使用最小花费爬楼梯_哔哩哔哩_bilibili
题解1动态规划
思路到达第 i 个台阶可以由第 i - 2个台阶跳2步也可以由第 i - 1个台阶跳1步到第 i 个台阶的最小花费为第到第 i - 2个台阶的最小花费加上第 i - 2个台阶的消费和到第 i - 1个台阶的最小花费加上第 i - 1个台阶的消费中小的那一方。
动态规划分析
dp 数组以及下标的含义dp[i] 为到达第 i 个台阶需要的最小花费。递推公式dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])。dp 数组初始化可以从0位置和1位置开始起跳即到达0位置和1位置的最小花费是0也就是 dp[0] 0dp[1] 0。遍历顺序从前到后。打印 dp 数组以输入为 [1,100,1,1,1,100,1,1,100,1] 为例dp 数组为 [ 0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 6 ]。
/*** param {number[]} cost* return {number}*/
var minCostClimbingStairs function(cost) {const dp new Array(cost.length 1);dp[0] 0;dp[1] 0;for (let 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)。
题解2动态规划优化
思路dp[i] 的状态由 dp[i - 1] 和 dp[i - 2] 决定可以用2个变量存储 dp[i - 1] 和 dp[i - 2]。
/*** param {number[]} cost* return {number}*/
var minCostClimbingStairs function(cost) {let a 0, b 0; // a 为到第 i - 2个台阶的最小花费b 为第 i - 1个台阶的最小花费for (let i 2; i cost.length; i) {const c Math.min(a cost[i - 2], b cost[i - 1]);a b; // 更新 ab c; // 更新 b}return b;
};
分析时间复杂度为 O(n)空间复杂度为 O(1)。
收获
练习动态规划的思想解决问题。
