Open xszi opened 3 years ago
本题注意理解题意:
i-1
级台阶的阶梯顶部。i
级台阶花费 cost[i]
,直接迈一大步跨过而不踏上去则不用花费。len
,那么楼顶就在下标为 len
第一步:定义子问题
踏上第 i
级台阶的体力消耗为到达前两个阶梯的最小体力消耗加上本层体力消耗:
最后迈 1 步踏上第 i 级台阶:dp[i-1] + cost[i]
最后迈 1 步踏上第 i 级台阶:dp[i-2] + cost[i]
第二步:实现需要反复执行解决的子子问题部分
所以踏上第 i 级台阶的最小花费为:
dp[i] = min(dp[i-2], dp[i-1]) + cost[i]
第三步:识别并求解出边界条件
// 第 0 级 cost[0] 种方案
dp[0] = cost[0]
// 第 1 级,有两种情况
// 1:分别踏上第0级与第1级台阶,花费cost[0] + cost[1]
// 2:直接从地面开始迈两步直接踏上第1级台阶,花费cost[1]
dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]
最后,翻译成代码求解,处理一些边界情况
let minCostClimbingStairs = function(cost) {
cost.push(0)
let dp = [], n = cost.length
dp[0] = cost[0]
dp[1] = cost[1]
for(let i = 2; i < n; i++){
dp[i] = Math.min(dp[i-2] , dp[i-1]) + cost[i]
}
return dp[n-1]
}
算法复杂度:
时间复杂度:O(n) 空间复杂度:O(n)
空间复杂度优化:
let minCostClimbingStairs = function(cost) {
let n = cost.length,
n1= cost[0],
n2 = cost[1]
for(let i = 2; i < n; i++){
dp[i] = Math.min(n1 , n2) + cost[i]
n1 = n2
n2 = dp[i]
}
return Math.min(n1 , n2)
}
空间复杂度:O(1)
数组的每个索引作为一个阶梯,第
i
个阶梯对应着一个非负数的体力花费值cost[i]
(索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为
0
或1
的元素作为初始阶梯。示例 1:
示例 2:
注意:
cost
的长度将会在[2, 1000]
。cost[i]
将会是一个Integer
类型,范围为[0, 999]
。leetcode