Example: Minimum Jumps To end of array - rFronteddu/general_wiki GitHub Wiki

You are given an array were each cell specifies the maximum cells you can jump from that cell. Determine the minimum number of jumps to reach the end of the array.

X: 2, 3, 1, 1, 2, 4, 2, 0 ,1 ,1 X[0..n-1]

Input:

0	1	2	3	4	5	6	7	8	9
2	3	1	1	2	3	2	0	1	1

First row is the minimum number of jumps to reach cell, second row is the previous cell

0	1	1	2	2	3	3	4	4	4
-1	0	0	0	1	1	4	4	5	5

We start with i in position 1 and j in position 0

• we check if j can reach i, if yes, we update the count if 1 + the number of steps needed to reach j is lower than the number of steps we previously calculated for i
• we proceed until j == i - 1
• we then increase i and repeat

// x[0..n-1]
minJumpToEnd(x)
    n = x.len
    let d[0..n-1] be an array
    let p[0..n-1] be an array
    d[0] = 0
    p[0] = -1

    for i = 1 to n-1
        d[i] = max
        for j = 0 to i - 1
            if j+x[j] >= i 
                // we can reach if from j
                q = 1 + d[j] // 1 (jump from j to i) + steps to reach j
                if q < d[i]
                    d[i] = q
                    p[i] = j // step used to reach i

    print("Number of jumps: " p[n])

    l = []
    while n != -1
        l.push(n)
        n = p[n]

    print(l)