'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 |
---|