题目

leetcode:746

代码与解析

本文思路借鉴carl大佬博客
b站一个魔性的up

  • 确定dp数组及下标含义

dp[i]:用来表示 到达第i个台阶所耗费的体力

  • 确定递推公式
    dp[i]由dp[i-1]和dp[i-2]表示

  • dp数组初始化

    dp := make([]int, len(cost))
    dp[0], dp[1] = cost[0], cost[1]

  • 遍历顺序
    因为是模拟台阶,而且dp[i]又dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了

  • 举例推导dp数组


    至于dp[i] = min(dp[i-1], dp[i-2]) + cost[i]要 + cost[i]
    因为是花费 而不是折扣

func minCostClimbingStairs(cost []int) int {
    dp := make([]int, len(cost))
    dp[0], dp[1] = cost[0], cost[1]
    for i:=2;i<len(cost);i++{
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
    }
    fmt.Println(dp)
    return min(dp[len(cost)-1], dp[len(cost)-2])
}
func min(a, b int)int{
    if a>b{
        return b
    }
    return a
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:864 天
  • 访问总数:475066 人次
ICP备案号: 辽ICP备20003309号