Dynamic Programming
LC #55Medium
Jump Game
Dynamic Programming
AmazonGoogleMetaMicrosoftProblem
Given an array where nums[i] is the maximum jump length from position i, determine if you can reach the last index.
arraygreedydynamic-programming
Constraints
- ›1 ≤ nums.length ≤ 10⁴
- ›0 ≤ nums[i] ≤ 10⁵
Example
Input
nums = [2, 3, 1, 1, 4]Output
trueWhy
Jump 1 step to index 1, then 3 steps to the last index