746.使用正常花费爬台阶（javascript）746.MinCostClimbingStairs

剑指 Offer II 088. 爬楼梯的最低成本

给你一个整数数组 cost ，其中 cost[i] 是从楼梯上 i 爬上台阶的费用。一旦你支付了这笔费用，你可以选择爬一两步。

你可以从下标中选择。 0 或下标为 1 台阶开始爬楼梯。

请计算并返回到达楼梯顶部的最低成本。

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

示例 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 。

Example 1:

Input: cost = [10,15,20] Output: 15 Explanation: You will start at
index 1.

• Pay 15 and climb two steps to reach the top.
  The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6 Explanation: You
will start at index 0.

• Pay 1 and climb two steps to reach index 2.
• Pay 1 and climb two steps to reach index 4.
• Pay 1 and climb two steps to reach index 6.
• Pay 1 and climb one step to reach index 7.
• Pay 1 and climb two steps to reach index 9.
• Pay 1 and climb one step to reach the top.
  The total cost is 6.

解决问题的过程来自： https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/shi-yong-zui-xiao-hua-fei-pa-lou-ti-by-l-ncf8/

假设数组 cost 的长度为 n，则 n 这些步骤分别对应于下标。 0 到 n−1，地板的顶部对应于下标 n，这个问题相当于计算下标。 n 最低成本。可以通过动态规划解决。

1. 创建长度 n+1 的数组 dp，其中 dp[i] 指示已到达下标。 i 最低成本。
2. 因为可以选择下标 0 或 1 作为初始阶梯 dp[0]=dp[1]=0。
3. 当 2≤i≤n 可以来自下标。 i-1使用 cost[i−1] 到达下标的成本 i，或从下标 i−2 使用 cost[i−2] 到达下标的成本 i为了最小化总成本，dp[i] 应取上述两项的最小值，因此状态转移方程如下：
   dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])

依次计算 dp 决赛中每个项目的价值 dp[n] 即为达到楼层顶部最低成本。

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

leetcode标题来源： https://leetcode-cn.com/problems/min-cost-climbing-stairs/