xqian
commented
10 years ago Why the method in 9b1fa9a works:
a) for every node the final least steps, jumps[i]; if j>I, then jumps[j]>=jumps[i] If this is not true, for example something like this exist: [.B.] 5 [.A.] 4 4 exist; Then in the A region, there must exist something smaller than 5 to jump to 4. Because jump to 4 from B region will make 5 be covered, thus 5 cannot be larger than 4. So if jumps[x]<5 exist in the past 5 region, there must be something even smaller between the 5 and that jump[x], then this smaller request another thing exist between 5 and itself, until the one next to 5. OK, the one next to 5 have to be smaller than 5, and how can this be achieved?
b) if the jumps always have "if j>I, then jumps[j]>jumps[i]", then the first touch is the best/least jump. For: i [A] j [B] [X] If i<j, and i can jump directly to X; then the path jump to X from j directly must not be less/better than the path from i; because jumps[j]>=jumps[i]
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example: Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
http://leetcode.com/onlinejudge#question_45