题目

题目来源：力扣（LeetCode）

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

思路分析

动态规划

  1. 确定 dp 数组以及下标的含义
    • 使用一维数组 dp[i] 来记录状态
    • dp[i] 的定义为，到达第 i 个台阶所花费的最少体力为 dp[i] ，注意第一步一定是要花费的
  2. 确定递推公式
    • 根据题意可知，得到 dp[i] 有两种途径，即 dp[i - 1] 和 dp[i - 2] ，dp[i - 1]对应的是从第 i - 1级迈一步到达第i级台阶时花费的体力，dp[i - 2] 对应的是从第 i - 2 级台阶迈两步跨过第 i-1 级台阶到达第 i 级台阶时花费的体力；
    • 要求最小值，那么一定是 dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] ，最后一个 cost[i] 对应题目中的要求——每当你爬上一个阶梯你需要支付相应的体力值
  3. dp 数组如何进行初始化
    • 我们从递推公式可以看出，要求出 dp[i] 我们需要知道 dp[i - 1] 和 dp[i - 2] ，因此我们需要初始化dp[0] 和 dp[1] 即可。
    • 初始化：dp[0] = cost[0] , dp[1] = cost[1]
  4. 确定遍历顺序
    • 本题的遍历顺序很简单，因为是模拟台阶，而且 dp[i] 是通过 dp[i - 1] 和 dp[i - 2] 推出，所以从前到后遍历 cost 数组即可。
  1. /**
  2.  * @param {number[]} cost
  3.  * @return {number}
  4.  */
  5. var minCostClimbingStairs = function (cost) {
  6.   let n = cost.length;
  7.   let dp = new Array(n + 1).fill(0);
  8.   // 根据题意添加元素0
  9.   cost.push(0);
  10.   // 初始化边界条件
  11.   dp[0] = cost[0], dp[1] = cost[1];
  12.   // 这里认为第一步不花费体力，最后一步花费体力
  13.   for (let i = 2; i <= n; i++) dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
  14.   return dp[n];
  15. };

参考阅读 https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/yi-bu-yi-bu-tui-dao-dong-tai-gui-hua-de-duo-chong-/ https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/dai-ma-sui-xiang-lu-dong-tai-gui-hua-wu-abbwz/ https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/shi-yong-zui-xiao-hua-fei-pa-lou-ti-java-syei/