← 返回 uber 的题目列表Jump Game with Prime-Step Rule (DP)
类型：online_judge
Problem: Prime-Step Jump Game (Jump Game Prime)
You are given an array nums of length n indexed from 0 to n-1. You start at index 0 and want to reach index n-1.
From position i, you may jump to any position j (j > i) if both conditions hold:
The step length d = j - i is a prime number.
d <= nums[i] (the maximum jump length allowed from index i).
Determine whether you can reach index n-1 from index 0.
Output true if reachable, otherwise output false.
Input Format
Line 1: integer n
Line 2: n integers nums[i]
Output Format
One line: true or false
Constraints
1 <= n <= 2e5
0 <= nums[i] <= 1e9
Examples
Example 1
Input:
5
2 3 1 1 0
Output:
true
Explanation:
From 0 you can jump by 2 (prime) to 2.
From 2 you can jump by 2 to 4 (the end).
Example 2
Input:
4
1 1 1 1
Output:
false
Explanation: All positions allow max jump length 1, but 1 is not prime, so you cannot move.
Example
Input
5
2 3 1 1 0
Output
true