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

Categories:

题目描述
思路分析
1. 解法一：滚动 DP（推荐）
相似题目

题目描述

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

思路分析

解法一：滚动 DP（推荐）

核心思路：

设 dp[i] 表示到达第 i 阶的最小花费。

转移：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。

只需保留前两阶的状态即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示阶梯数。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = 0;
        int prev1 = 0;

        for (int i = 2; i <= n; i++) {
            int cur = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
}

func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	prev2, prev1 := 0, 0

	for i := 2; i <= n; i++ {
		cur := prev1 + cost[i-1]
		if prev2+cost[i-2] < cur {
			cur = prev2 + cost[i-2]
		}
		prev2 = prev1
		prev1 = cur
	}

	return prev1
}

相似题目

题目	难度	考察点
70. 爬楼梯	简单	动态规划
198. 打家劫舍	中等	动态规划
213. 打家劫舍 II	中等	动态规划
740. 删除并获得点数	中等	动态规划
509. 斐波那契数	简单	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/42745447