Skip to content

Commit 6c48044

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0746. Min Cost Climbing Stairs
1 parent 5b9a614 commit 6c48044

File tree

8 files changed

+134
-36
lines changed

8 files changed

+134
-36
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -158,7 +158,10 @@
158158

159159
### 动态规划
160160

161+
- [斐波那契数](./solution/0500-0599/0509.Fibonacci%20Number/README.md)
162+
- [第 N 个泰波那契数](./solution/1100-1199/1137.N-th%20Tribonacci%20Number/README.md)
161163
- [爬楼梯](./solution/0000-0099/0070.Climbing%20Stairs/README.md)
164+
- [使用最小花费爬楼梯](./solution/0700-0799/0746.Min%20Cost%20Climbing%20Stairs/README.md)
162165
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
163166
- [最大子序和](./solution/0000-0099/0053.Maximum%20Subarray/README.md)
164167
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)

‎README_EN.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -152,7 +152,10 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
152152

153153
### Dynamic Programming
154154

155+
- [Fibonacci Number](./solution/0500-0599/0509.Fibonacci%20Number/README_EN.md)
156+
- [N-th Tribonacci Number](./solution/1100-1199/1137.N-th%20Tribonacci%20Number/README_EN.md)
155157
- [Climbing Stairs](./solution/0000-0099/0070.Climbing%20Stairs/README_EN.md)
158+
- [Min Cost Climbing Stairs](./solution/0700-0799/0746.Min%20Cost%20Climbing%20Stairs/README_EN.md)
156159
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
157160
- [Maximum Subarray](./solution/0000-0099/0053.Maximum%20Subarray/README_EN.md)
158161
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)

‎solution/0700-0799/0746.Min Cost Climbing Stairs/README.md

Lines changed: 46 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -53,12 +53,10 @@
5353
```python
5454
class Solution:
5555
def minCostClimbingStairs(self, cost: List[int]) -> int:
56-
pre = cur = 0
57-
n = len(cost)
58-
for i in range(1, n):
59-
t = min(cost[i] + cur, cost[i - 1] + pre)
60-
pre, cur = cur, t
61-
return cur
56+
a = b = 0
57+
for i in range(1, len(cost)):
58+
a, b = b, min(a + cost[i - 1], b + cost[i])
59+
return b
6260
```
6361

6462
### **Java**
@@ -68,17 +66,53 @@ class Solution:
6866
```java
6967
class Solution {
7068
public int minCostClimbingStairs(int[] cost) {
71-
int pre = 0, cur = 0;
72-
for (int i = 1, n = cost.length; i < n; ++i) {
73-
int t = Math.min(cost[i] + cur, cost[i - 1] + pre);
74-
pre = cur;
75-
cur = t;
69+
int a = 0, b = 0;
70+
for (int i = 1; i < cost.length; ++i) {
71+
int c = Math.min(a + cost[i - 1], b + cost[i]);
72+
a = b;
73+
b = c;
7674
}
77-
return cur;
75+
return b;
7876
}
7977
}
8078
```
8179

80+
### **C++**
81+
82+
```cpp
83+
class Solution {
84+
public:
85+
int minCostClimbingStairs(vector<int>& cost) {
86+
int a = 0, b = 0;
87+
for (int i = 1; i < cost.size(); ++i) {
88+
int c = min(a + cost[i - 1], b + cost[i]);
89+
a = b;
90+
b = c;
91+
}
92+
return b;
93+
}
94+
};
95+
```
96+
97+
### **Go**
98+
99+
```go
100+
func minCostClimbingStairs(cost []int) int {
101+
a, b := 0, 0
102+
for i := 1; i < len(cost); i++ {
103+
a, b = b, min(a+cost[i-1], b+cost[i])
104+
}
105+
return b
106+
}
107+
108+
func min(a, b int) int {
109+
if a < b {
110+
return a
111+
}
112+
return b
113+
}
114+
```
115+
82116
### **...**
83117

84118
```

‎solution/0700-0799/0746.Min Cost Climbing Stairs/README_EN.md

Lines changed: 46 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -45,30 +45,64 @@
4545
```python
4646
class Solution:
4747
def minCostClimbingStairs(self, cost: List[int]) -> int:
48-
pre = cur = 0
49-
n = len(cost)
50-
for i in range(1, n):
51-
t = min(cost[i] + cur, cost[i - 1] + pre)
52-
pre, cur = cur, t
53-
return cur
48+
a = b = 0
49+
for i in range(1, len(cost)):
50+
a, b = b, min(a + cost[i - 1], b + cost[i])
51+
return b
5452
```
5553

5654
### **Java**
5755

5856
```java
5957
class Solution {
6058
public int minCostClimbingStairs(int[] cost) {
61-
int pre = 0, cur = 0;
62-
for (int i = 1, n = cost.length; i < n; ++i) {
63-
int t = Math.min(cost[i] + cur, cost[i - 1] + pre);
64-
pre = cur;
65-
cur = t;
59+
int a = 0, b = 0;
60+
for (int i = 1; i < cost.length; ++i) {
61+
int c = Math.min(a + cost[i - 1], b + cost[i]);
62+
a = b;
63+
b = c;
6664
}
67-
return cur;
65+
return b;
6866
}
6967
}
7068
```
7169

70+
### **C++**
71+
72+
```cpp
73+
class Solution {
74+
public:
75+
int minCostClimbingStairs(vector<int>& cost) {
76+
int a = 0, b = 0;
77+
for (int i = 1; i < cost.size(); ++i) {
78+
int c = min(a + cost[i - 1], b + cost[i]);
79+
a = b;
80+
b = c;
81+
}
82+
return b;
83+
}
84+
};
85+
```
86+
87+
### **Go**
88+
89+
```go
90+
func minCostClimbingStairs(cost []int) int {
91+
a, b := 0, 0
92+
for i := 1; i < len(cost); i++ {
93+
a, b = b, min(a+cost[i-1], b+cost[i])
94+
}
95+
return b
96+
}
97+
98+
func min(a, b int) int {
99+
if a < b {
100+
return a
101+
}
102+
return b
103+
}
104+
```
105+
72106
### **...**
73107

74108
```

‎solution/0700-0799/0746.Min Cost Climbing Stairs/Solution.cpp

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
class Solution {
2+
public:
3+
int minCostClimbingStairs(vector<int>& cost) {
4+
int a = 0, b = 0;
5+
for (int i = 1; i < cost.size(); ++i) {
6+
int c = min(a + cost[i - 1], b + cost[i]);
7+
a = b;
8+
b = c;
9+
}
10+
return b;
11+
}
12+
};

‎solution/0700-0799/0746.Min Cost Climbing Stairs/Solution.go

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
func minCostClimbingStairs(cost []int) int {
2+
a, b := 0, 0
3+
for i := 1; i < len(cost); i++ {
4+
a, b = b, min(a+cost[i-1], b+cost[i])
5+
}
6+
return b
7+
}
8+
9+
func min(a, b int) int {
10+
if a < b {
11+
return a
12+
}
13+
return b
14+
}

‎solution/0700-0799/0746.Min Cost Climbing Stairs/Solution.java

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
11
class Solution {
22
public int minCostClimbingStairs(int[] cost) {
3-
int pre = 0, cur = 0;
4-
for (int i = 1, n = cost.length; i < n; ++i) {
5-
int t = Math.min(cost[i] + cur, cost[i - 1] + pre);
6-
pre = cur;
7-
cur = t;
3+
int a = 0, b = 0;
4+
for (int i = 1; i < cost.length; ++i) {
5+
int c = Math.min(a + cost[i - 1], b + cost[i]);
6+
a = b;
7+
b = c;
88
}
9-
return cur;
9+
return b;
1010
}
1111
}

‎solution/0700-0799/0746.Min Cost Climbing Stairs/Solution.py

Lines changed: 4 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,6 @@
11
class Solution:
22
def minCostClimbingStairs(self, cost: List[int]) -> int:
3-
pre = cur = 0
4-
n = len(cost)
5-
for i in range(1, n):
6-
t = min(cost[i] + cur, cost[i - 1] + pre)
7-
pre, cur = cur, t
8-
return cur
3+
a = b = 0
4+
for i in range(1, len(cost)):
5+
a, b = b, min(a + cost[i - 1], b + cost[i])
6+
return b

0 commit comments

Comments
 (0)