Nhảy Tới Đích Ít Bước Nhất
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một mảng $N$ số nguyên không âm $a_0, a_1, \dots, a_{N-1}$. Bạn đang đứng ở vị trí $0$ và muốn đi tới vị trí $N-1$. Tại vị trí $i$, bạn có thể nhảy tiến tới tối đa $a_i$ bước (tức là tới bất kỳ vị trí $j$ nào thỏa $i < j \le \min(N-1, i + a_i)$).
Hãy tìm số bước nhảy ít nhất để tới được vị trí $N-1$. Nếu không thể tới đích, in ra -1.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên không âm $a_0, \dots, a_{N-1}$ ($0 \le a_i \le 10^5$).
Dữ liệu ra
- In ra số bước nhảy ít nhất hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 5\n2 3 1 1 4 | 2 |
| 5\n3 2 1 0 4 | -1 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le a_i \le 10^5$
Community Discussion