746. Min Cost Climbing Stairs

Leetcode link

题目简介

/**
 * @param {number[]} cost
 * @return {number}
 */

题目给我们一个数字数组 cost

代表我们要从该位置离开所需要付出的代价，一旦我们付了代价，我们可以选择往前走一步或者两步

题目要求我们返回走到最后最少需要付出多少代价

解题思路

这题我们需要用到动态规划的思路来求解

状态转移方程为：dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i]

由于这一道题只会需要用到前两个状态，所以我们可以把 dp 数组优化成两个变量

最后，当遍历完 cost 数组后，我们把最后两个状态取最小即可

Javascript

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    let prev1 = cost[0]
    let prev2 = cost[1]

    for(let i=2;i<cost.length;i++) {
        let cur = Math.min(prev1, prev2) + cost[i]
        prev1 = prev2
        prev2 = cur
    }

    return Math.min(prev1, prev2)
};

复杂度分析

时间

O(n)

空间

O(1)