leetcode 746. Min Cost Climbing Stairs
LeetCode min cost
2023-09-14 09:11:53 时间
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:
cost
will have a length in the range[2, 1000]
.- Every
cost[i]
will be an integer in the range[0, 999]
.
class Solution(object): def minCostClimbingStairs(self, cost): """ :type cost: List[int] :rtype: int """ # mincost = min(mincost(n-1), mincost(n-2))+cost[n] # n = 2 a = cost[0] b = cost[1] for i in range(2, len(cost)): b,a = min(a, b)+cost[i], b return min(b, a)
注意:本质上是dp,dp[i]表示经过step i的min cost。
那么最后一步cost应该是min(dp[i], dp[i-1]) 表示要么最后一步是踩step i,cost就是dp[i],要么不踩step[i],必然是从step i-1过来的,跨了两步。
空间O(n)的解法:
Solution #1: Bottom-Up dynamic programming Let dp[i] be the minimum cost to reach the i-th stair. Base cases: dp[0]=cost[0] dp[1]=cost[1] DP formula: dp[i]=cost[i]+min(dp[i-1],dp[i-2]) Note: the top floor n can be reached from either 1 or 2 stairs away, return the minimum. class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n=(int)cost.size(); vector<int> dp(n); dp[0]=cost[0]; dp[1]=cost[1]; for (int i=2; i<n; ++i) dp[i]=cost[i]+min(dp[i-2],dp[i-1]); return min(dp[n-2],dp[n-1]); } };
或者是:
class Solution { public int minCostClimbingStairs(int[] cost) { int [] mc = new int[cost.length + 1]; mc[0] = cost[0]; mc[1] = cost[1]; for(int i = 2; i <= cost.length; i++){ int costV = (i==cost.length)?0:cost[i]; mc[i] = Math.min(mc[i-1] + costV, mc[i-2] + costV); } return mc[cost.length]; } }
相关文章
- Java实现 LeetCode 799 香槟塔 (暴力模拟)
- Java实现 LeetCode 640 求解方程(计算器的加减法计算)
- Java实现 LeetCode 541 反转字符串 II(暴力大法)
- Java实现 LeetCode 283 移动零
- (LeetCode 53)Maximum Subarray
- LeetCode(71):简化路径
- 【LeetCode 4】寻找两个有序数组的中位数
- Leetcode 1535. 找出数组游戏的赢家(尽力了)
- Leetcode 209. 长度最小的子数组
- LeetCode Climbing Stairs
- [Leetcode]-Min Stack
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- LeetCode 25. K 个一组翻转链表
- 【LeetCode】110. 平衡二叉树
- 【LeetCode】78. 子集