动画制作软件flash_广州企业年报网上申报入口_什么软件可以发布广告信息_环球网广东疫情最新消息

1. 题目链接

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

2. 题目描述

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

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

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

3. 题目示例

示例 1 :

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2 :

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

4. 解题思路

采用动态规划 + 记忆化搜索（自顶向下递归）。核心思想是：

• 到达第 i 阶的最小花费等于从第 i-1 阶爬 1 步（支付 cost[i-1]）或从第 i-2 阶爬 2 步（支付 cost[i-2]）的最小值。

状态转移方程：

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

关键步骤：

1. 递归函数 dfs(i) 计算到达第 i 阶的最小花费。
2. 记忆化数组 memo 缓存已计算的子问题结果，避免重复计算。
3. 递归终止条件：当 i <= 1 时，无需支付费用（可直接作为起点）。

5. 题解代码

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] memo = new int[n + 1];      // 初始化记忆化数组（大小为 n+1，表示到达第 i 阶的最小花费）Arrays.fill(memo, -1);           // 初始标记为未计算状态return dfs(n, memo, cost);       // 从目标台阶 n 开始递归}private int dfs(int i, int[] memo, int[] cost) {if (i <= 1) {                     // 递归终止条件：0 或 1 阶可直接到达，无需花费return 0;}if (memo[i] != -1) {              // 已计算过，直接返回缓存结果return memo[i];}// 计算两种选择的最小值：从 i-1 阶爬 1 步，或从 i-2 阶爬 2 步int res1 = dfs(i - 1, memo, cost) + cost[i - 1];  // 支付 i-1 阶的费用int res2 = dfs(i - 2, memo, cost) + cost[i - 2];  // 支付 i-2 阶的费用return memo[i] = Math.min(res1, res2);            // 结果存入缓存并返回}
}

6. 复杂度分析

时间复杂度：
每个台阶的状态仅计算一次，时间复杂度为 O(n)。

空间复杂度：

• 递归调用栈深度为 O(n)（最坏情况）。
• 记忆化数组占用 O(n) 空间。
  综上，空间复杂度为 O(n)。