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

一、题目

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];
    }
};