友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
746. Min Cost Climbing Stairs
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].Note:
-
costwill have a length in the range[2, 1000]. -
Every
cost[i]will be an integer in the range[0, 999].
思路分析
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-11 20:23:46
*/
public int minCostClimbingStairs(int[] cost) {
// dp[i] 表示到底第 i 阶时，所需最少费用
int[] dp = new int[cost.length + 1];
// 0 和 1 可以直接站上，所以不需要付费
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i < dp.length; i++) {
// 第 i 阶，有两种走法
// 1. 从第 i-1 阶走一步上去，花费： dp[i-1] 走到 i-1 的费用 + cost[i-1]（向上的费用）
// 2. 从第 i-2 阶走两步上去，花肥： dp[i-2] 走到 i-2 的费用 + cost[i-2]（向上的费用）
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[dp.length - 1];
}