Dynamic Programming
LC #45Medium
Jump Game II
Dynamic Programming
AmazonGoogleMetaBloombergProblem
Find the minimum number of jumps to reach the last index (you are guaranteed to reach it).
arraygreedydynamic-programming
Constraints
- ›1 ≤ nums.length ≤ 10⁴
- ›0 ≤ nums[i] ≤ 1000
- ›Always possible to reach last index
Example
Input
nums = [2, 3, 1, 1, 4]Output
2Why
Minimum 2 jumps: index 0 → index 1 → index 4