到达末端的最小跳跃次数动态编程MIG

Question

给定一个数组，从第一个元素开始验证到达终点需要多少步。

示例：arr=[1,3,5,8,4,2,6,7,0,7,9]

1-

3个步骤。

到目前为止，我从极客那里得到了以下代码：

def jumpCount(x, n): 
  jumps = [0 for i in range(n)] 

  if (n == 0) or (x[0] == 0): 
      return float('inf') 

  jumps[0] = 0


  for i in range(1, n): 
      jumps[i] = float('inf')   
      for j in range(i): 
          if (i <= j + x[j]) and (jumps[j] != float('inf')): 
              jumps[i] = min(jumps[i], jumps[j] + 1) 
              break                 
  return jumps[n-1]     

def jumps(x):
  n = len(x)
  return jumpCount(x,n) 

x = [1, 3, 5, 8, 4, 2, 6, 7, 0, 7, 9]

print(jumps(x))

但是我想打印出哪些数字是最短的路径（1-3-8）。我如何调整代码来做到这一点？

我试图创建一个j的列表，但是由于5在循环中进行了测试，所以也添加了它。

问题的链接：https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

Answer 1

基本思想是，您需要一个辅助结构来帮助您跟踪最小路径。这些类型的结构通常被称为“backpointers”（在我们的例子中，你可以称它们为“forwardpointers”，因为我们正在前进，duh）。我的代码递归地解决了这个问题，但同样的问题也可以迭代地解决。策略如下：

jumps_vector = [ 1, 3, 5, 8, 4, 2, 6, 7, 0, 7, 9 ]

"""
fwdpointers holds the relative jump size to reach the minimum number of jumps
for every component of the original vector
"""
fwdpointers = {}

def jumps( start ):
    if start == len( jumps_vector ) - 1:
        # Reached the end
        return 0
    if start > len( jumps_vector ) - 1:
        # Cannot go through that path
        return math.inf
    if jumps_vector[ start ] == 0:
        # Cannot go through that path (infinite loop with itself)
        return math.inf

    # Get the minimum in a traditional way
    current_min = jumps( start + 1 )
    fwdpointers[ start ] = start + 1
    for i in range( 2, jumps_vector[ start ] + 1 ):
        aux_min = jumps( start + i )
        if current_min > aux_min:
            # Better path. Update minimum and fwdpointers
            current_min = aux_min
            # Store the (relative!) index of where I jump to
            fwdpointers[ start ] = i

    return 1 + current_min

在这种情况下，变量fwdpointers存储我跳转到的位置的相对索引。例如，fwdpointers[0]=1，因为我将跳转到相邻的数字，但是fwdpointers[1]=2，因为我将在下一次跳转时跳转两个数字。

完成此操作后，只需在main（）函数上稍微进行后处理即可：

if __name__ == "__main__":
    min_jumps = jumps( 0 )
    print( min_jumps )

    # Holds the index of the jump given such that
    # the sequence of jumps are the minimum
    i = 0
    # Remember that the contents of fwdpointers[ i ] are the relative indexes
    # of the jump, not the absolute ones
    print( fwdpointers[ 0 ] )
    while i in fwdpointers and i + fwdpointers[ i ] < len( jumps_vector ):
        print( jumps_vector[ i + fwdpointers[ i ] ] )
        # Get the index of where I jump to
        i += fwdpointers[ i ]
        jumped_to = jumps_vector[ i ]

我希望这回答了你的问题。

编辑：我认为迭代版本更具可读性：

results = {}
backpointers = {}
def jumps_iter():
    results[ 0 ] = 0
    backpointers[ 0 ] = -1
    for i in range( len( jumps_vector ) ):
        for j in range( 1, jumps_vector[ i ] + 1 ):
            if ( i + j ) in results:
                results[ i + j ] = min( results[ i ] + 1, results[ i + j ] )
                if results[ i + j ] == results[ i ] + 1:
                    # Update where I come from
                    backpointers[ i + j ] = i
            elif i + j < len( jumps_vector ):
                results[ i + j ] = results[ i ] + 1
                # Set where I come from
                backpointers[ i + j ] = i

    return results[ len( jumps_vector ) - 1 ]

以及后处理：

i = len( jumps_vector ) - 1
print( jumps_vector[ len( jumps_vector ) - 1 ], end = " " )
while backpointers[ i ] >= 0:
    print( jumps_vector[ backpointers[ i ] ], end = " " )
    i = backpointers[ i ]
print()