'minimum number of jumps dynamic programming

I wrote this code to solve a problem called minimum number of jumps which basically asks what are the minimum number of jumps it takes to get from the beginning of the array at i=0 to the end of the array at i = length of array - 1.

The idea is that you can jump up to a[i] spaces or can choose to jump to a space less than i + a[i] and whichever you choose will be considered 1 jump.

Example: a = [3, 4, 2, 1, 2, 3, 7, 1, 1, 1, 3]

answer is 3 -> (4 or 2) -> (2 or 3) -> 7 -> 3

which then gives 4 jumps as an answer. I actually get 5 instead with my solution. I am not sure why I am not getting the minimum. First off I do not know if I am using the right approach but I figured a lot of dynamic programming problems are solved using a 2d array so I tried it and I figured I am very close to the solution but having some difficulty as to where I am wrong.

def minNumberOfJumps(array):
    minJumps = [[float('inf') for _ in range(len(array))]
                for _ in range(len(array))]

    for row in minJumps:
        row[0] = 0

    for col in range(1, len(minJumps[0])):
        if array[0] >= col:
            minJumps[0][col] = 1

    for row in range(1, len(minJumps)):
        jumpChanged = False
        for col in range(1, len(minJumps[row])):
            jump = array[row] + row

            if minJumps[row - 1][col] != float('inf'):
                minJumps[row][col] = minJumps[row - 1][col]
            elif not jumpChanged and jump <= col:
                minJumps[row][col] = minJumps[row - 1][col - 1] + 1
                jumpChanged = True
            elif jump >= col:
                minJumps[row][col] = minJumps[row][col - 1]

    return minJumps[-1][-1]

The idea behind my solution is I add 1 when I need to jump. Going to any index

say original array is a, then i <= i + a[i], consider it 1 jump, otherwise, if we have reached an index i, where i > i + a[i] position is not reachable (i label it as infinity in 2d array b)

if we are looking at rows 1 up to the length of b - 1 then we always check the minimum number of jumps it took us to get to the current position one row before at b[i - 1][j] and take that number. If that number is infinity and we can make a jump meaning current column, j, we are looking at is j <= to i + a[i] then we add 1 to the previous jump, b[i - 1][j - 1]. If we have tried making a jump already than I only update the other values for all other positions i can jump to with the value at b[i][j - 1], or basically from the column before.

I believe I have explained this correctly but I do not know why I am not right with my way of thinking.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source