Skip to content

Latest commit

 

History

History
65 lines (52 loc) · 1.73 KB

746.使用最小花费爬楼梯.md

File metadata and controls

65 lines (52 loc) · 1.73 KB

746.使用最小花费爬楼梯

/*
 * @lc app=leetcode.cn id=746 lang=typescript
 *
 * [746] 使用最小花费爬楼梯
 */

// @lc code=start
function minCostClimbingStairs(cost: number[]): number {}
// @lc code=end

解法 1: 动态规划

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)
  1. 子问题: 求到达第 i 个阶梯最小的体力
  2. 状态:
    • dp[i]: 代表到达第 i 个阶梯的最小体力
  3. DP 方程:
    • dp[i]= min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
  4. 边界:
    • dp[0] = 0
    • dp[1] = 0
function minCostClimbingStairs(cost: number[]): number {
  const dp = [0, 0]
  for (let i = 2; i <= cost.length; i++) {
    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  }

  return dp[dp.length - 1]
}

优化空间

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)
function minCostClimbingStairs(cost: number[]): number {
  let [pre, cur] = [0, 0]
  for (let i = 2; i <= cost.length; i++) {
    ;[cur, pre] = [Math.min(cur + cost[i - 1], pre + cost[i - 2]), cur]
  }

  return cur
}

Case

test.each([
  { input: { cost: [10, 15, 20] }, output: 15 },
  { input: { cost: [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] }, output: 6 },
])(`input: cost = $input.cost`, ({ input: { cost }, output }) => {
  expect(minCostClimbingStairs(cost)).toBe(output)
})