使用最小花费爬楼梯

746. 使用最小花费爬楼梯

leetcode 链接

思路：

动态规划

1. dp[i] 表示到达下标为 i 的台阶，需要的最低花费。

2. 确定初始值，dp[0] = 0, dp[1] = 0。

3. 确定遍历顺序，从前往后遍历。

4. 确定转移方程，dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])。

5. 确定结束条件，遍历到最后一个台阶。返回 dp[costLen] 即可。

typescript 解法

function minCostClimbingStairs(cost: number[]): number {
  const costLen: number = cost.length;
  // dp[i] 为达到下标为i所需要的最低花费
  let dp: number[] = new Array(costLen + 1).fill(0);
  if (costLen < 2) {
    return 0;
  }
  for (let i: number = 2; i < dp.length; i++) {
    dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
  }
  return dp[costLen];
}

go 解法

func minCostClimbingStairs(cost []int) int {
    // dp为到达下标为i的台阶，需要的最低花费
    dp := make([]int, len(cost) + 1)
    if len(cost) < 2 {
        return 0
    }
    // 初始化dp数组
    dp[0] = 0
    dp[1] = 0
    // 确定遍历顺序
    for i := 2; i < len(cost) + 1; i ++ {
        // 确定转移方程
        dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])
    }
    return dp[len(cost)]

}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}