🍥

Hang Zhang

genius.

Data Structure and Algorithm

Min Cost Climbing Stairs

746. 使用最小花费爬楼梯

分析

状态定义：
- 定义 f[i] 为到达第 i 个台阶的最低花费
状态转移：
- 每次可以从前一个台阶爬上来，也可以从前两个台阶爬上来，选择花费较小的一种：f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2])
初始状态：
- f[0] = 0 ：第 0 台阶为起点，不需要任何花费
- f[1] = 0 ：第 1 台阶为起点，也不需要任何花费
目标：
- 返回 f[n] ，即爬到楼梯顶部的最小花费

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution
{
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        int n = cost.size();
        std::vector<int> f(n + 1); // DP 数组，大小为 n+1

        // 从第 2 个台阶开始计算最低花费
        for (int i = 2; i <= n; ++i)
            f[i] = std::min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);

        return f[n]; // 返回到达顶部的最小花费
    }
};