博客

原文地址：

http://www.iming.top/details/7

定义一个dp数组， dp[i] 表示踩到 第 i 个台阶要花费的值， 注意，一定要踩到。

所有到这个台阶的最小花费： dp[i] =min( dp[i-2] + i, dp[i-1] + i)

代码如下：

function minCostClimbingStairs(cost: number[]): number {

    if (cost.length === 2) { return cost[0] > cost[1] ? cost[1] : cost[0] }

    let dp = [cost[0], cost[1]];
    for(let i = 2; i < cost.length; i++) {
        dp[i] = Math.min(dp[i-2] + cost[i], dp[i-1] +cost[i]);
    }

    return Math.min(dp[cost.length - 1], dp[cost.length - 2]);;
};

但是其实我们只维护 dp[i-1] 和 dp[i – 2] 就行，代码如下：

function minCostClimbingStairs(cost: number[]): number {

    if (cost.length === 2) { return cost[0] > cost[1] ? cost[1] : cost[0] }

    let pre_2 = cost[0];
    let pre_1 = cost[1];

    for(let i = 2; i < cost.length; i++) {
        const temp = pre_1;
        pre_1 = Math.min(pre_2 + cost[i], pre_1 +cost[i]);
        pre_2 = temp;
    }

    return pre_2 > pre_1 ? pre_1 : pre_2
};