Nhảy Tới Đích Ít Bước Nhất

Buổi 21 — DP 1D cổ điển Dynamic Programming greedy
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved