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

2023-12-18 05:43:32

一、题目

1、题目描述

给你一个整数数组?cost?,其中?cost[i]?是从楼梯第?i?个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为?0?或下标为?1?的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

2、接口描述

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

3、原题链接

746. 使用最小花费爬楼梯


二、解题报告

1、思路分析

动态规划入门问题,设计dp[i]为到达第i阶台阶的最小花费,那么可得出递推:

dp[i[ = min(dp[i-1] , dp[i-2]) + cost[i]

最后返回dp[n]即可

注意每次状态转移只跟上一次状态有关,所以我们可以用滚动数组优化为O(1)

2、复杂度

时间复杂度:O(n) 空间复杂度:O(1)

3、代码详解

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp[2]{0} , tmp;
        dp[0] = cost[0] , dp[1] = cost[1];
        cost.emplace_back(0);
        for(int i = 2 , n = cost.size() ; i < n ; i++)
        {
            tmp = dp[1];
            dp[1] = min(dp[0] , dp[1]) + cost[i];
            dp[0] = tmp;
        }
        return dp[1];
    }
};

文章来源:https://blog.csdn.net/EQUINOX1/article/details/135052396
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。