Chi Phí Leo Thang Tối Thiểu
Points
11
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Một cầu thang có $N$ bậc được đánh số từ $0$ đến $N-1$, bậc thứ $i$ có chi phí là $cost[i]$. Sau khi trả chi phí tại bậc $i$, bạn có thể bước lên $1$ hoặc $2$ bậc.
Bạn có thể bắt đầu từ bậc $0$ hoặc bậc $1$ (không mất phí vào bậc xuất phát, chỉ mất phí khi rời khỏi bậc đó). Hãy tìm tổng chi phí nhỏ nhất để lên tới đỉnh cầu thang (vị trí $N$).
Công thức quy hoạch động: $dp[i] = \min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])$.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($2 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên không âm $cost[0], cost[1], \dots, cost[N-1]$ ($0 \le cost[i] \le 10^4$).
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất để tới đỉnh $N$.
Ví dụ
| Input | Output |
|---|---|
| 3\n10 15 20 | 15 |
| 10\n1 100 1 1 1 100 1 1 100 1 | 6 |
Giới hạn
- $2 \le N \le 10^5$
- $0 \le cost[i] \le 10^4$
Community Discussion