跳到主要内容

746.使用最小花费爬楼梯

链接：746.使用最小花费爬楼梯
难度：Easy
标签：数组、动态规划
简介：给你数组的每个索引作为一个阶梯，第  i 个阶梯对应着一个非负数的体力花费值  cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。

题解 1 - typescript​

  • 编辑时间：2020-12-22
  • 执行用时：88ms
  • 内存消耗：40.7MB
  • 编程语言：typescript
  • 解法介绍：偶数列倒序插入。
function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (root === null) return [];
  const ans: number[][] = [[root.val]];
  let queue = [root];
  let height = 0;
  let size = 1;
  while (queue.length !== 0) {
    const node = queue.shift()!;
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
    if (--size === 0) {
      size = queue.length;
      queue.length !== 0 &&
        ans.push((++height & 1 ? queue.slice().reverse() : queue).map(node => node.val));
    }
  }
  return ans;
}

题解 2 - typescript​

  • 编辑时间：2021-09-03
  • 执行用时：80ms
  • 内存消耗：39.9MB
  • 编程语言：typescript
  • 解法介绍：动态规划。
function minCostClimbingStairs(cost: number[]): number {
  const n = cost.length;
  const dp = new Array(n + 1);
  dp[0] = cost[0];
  dp[1] = cost[1];
  for (let i = 2; i <= n; i++) dp[i] = (cost[i] ?? 0) + Math.min(dp[i - 1], dp[i - 2]);
  return dp[n];
}

题解 3 - python​

  • 编辑时间：2023-12-17
  • 执行用时：48ms
  • 内存消耗：16.2MB
  • 编程语言：python
  • 解法介绍：dp。
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        cost.append(0)
        n = len(cost)
        dp = [0] * n
        dp[0] = cost[0]
        dp[1] = cost[1]
        for i in range(2, n):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
        return dp[n - 1]