题目地址(746. 使用最小花费爬楼梯)

https://leetcode-cn.com/problems/min-cost-climbing-stairs/

题目描述

  1. 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
  3. 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
  5. 请你计算并返回达到楼梯顶部的最低花费。
  9. 示例 1：
  11. 输入：cost = [10,15,20]
  12. 输出：15
  13. 解释：你将从下标为 1 的台阶开始。
  14. - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
  15. 总花费为 15 。
  18. 示例 2：
  20. 输入：cost = [1,100,1,1,1,100,1,1,100,1]
  21. 输出：6
  22. 解释：你将从下标为 0 的台阶开始。
  23. - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
  24. - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
  25. - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
  26. - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
  27. - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
  28. - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
  29. 总花费为 6 。
  34. 提示：
  36. 2 <= cost.length <= 1000
  37. 0 <= cost[i] <= 999

前置知识


公司

  • 暂无

思路

image.png
0 和 1的花费就是他本身 从二开始 他的花费就是前两个之间比较小的那个加上他本身
最终返回的登上楼梯的数也是 最后两个最小的数

dp数组的含义就是
到达第i个台阶所花费的最少体力为dp[i]


代码

  • 语言支持：Java

Java Code:


class Solution {
        public int minCostClimbingStairs(int[] cost) {
            //1定义dp数组
            int[] dp = new int[cost.length];
            //数组的初始化
            dp[0] =cost[0];
            dp[1] =cost[1];
            //从2开始
            for (int i = 2; i < dp.length; i++) {
                //状态转移方程
                dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i];
            }
            return Math.min(dp[cost.length-1],dp[cost.length-2]);
        }
    }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：746. 使用最小花费爬楼梯 - 图2#card=math&code=O%28n%29&id=wgdg7)
  • 空间复杂度：746. 使用最小花费爬楼梯 - 图3#card=math&code=O%28n%29&id=QzfEF)