### [746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/?envType=daily-question&envId=2023-10-13)

# 1. Tóm tắt đề bài

Cho một mảng `cost` với `cost[i]` chính là giá phải trả khi bước vào nấc thang thứ `i` trên một chiếc cầu thang. Sau khi trả giá cho nấc thang thứ `i`, bạn có thể lựa chọn tiến $1$ hoặc $2$ bước.

Bạn có thể bắt đầu từ nấc thang $0$ hoặc $1$ và trả tiền cho nấc đó.

Hãy tính tổng giá trị nhỏ nhất sau khi đi hết nấc thang cuối.

##### Giới hạn

- $2 \le cost.length \le 1000$.
- $0 \le cost[i] \le 999$.

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n)$**

Đây là một bài $dp$ căn bản, khi mà kết quả khi tính đến bậc thang thứ $i$ ($i \ge 2$) sẽ được tính dựa vào kết quả $i - 1$ và $i - 2$. Vì vậy, bài này sẽ có chút hình hài của Fibonacci.

# 3. Lời giải chi tiết

Ta định nghĩa $f(i)$ là giá trị nhỏ nhất phải trả khi đi đến nấc thang thứ $i$.

Công thức tính như sau:

- $f(0) = cost[0]$.
- $f(1) = cost[1]$.
- $f(i) = cost[i] + max(f[i - 1], f[i - 2]) \forall i: 1 < i < n$.

Kết quả chính là $max(f[n - 1], f[n - 2])$.

Như trong code mẫu của mình, mình đã gán giá trị trên vào chính $f[n]$.

### Độ phức tạp thuật toán

Thời gian: $O(n)$.

Bộ nhớ mở rộng: $O(n)$.

### [Code mẫu](https://leetcode.com/problems/min-cost-climbing-stairs/submissions/1073954648/?envType=daily-question&envId=2023-10-13)

# 4. Kết luận & Gợi ý mở rộng

Các bạn có thể tham khảo các bài QHĐ rất dễ ở dưới đây:

[509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)
[118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)
[1025. Divisor Game](https://leetcode.com/problems/divisor-game/)

Hoặc xem chuyên đề #0 của mình.