达到终点的最小跳转数

Question

给定一个数组，从第一个元素中验证需要多少步骤才能到达终点。

示例: arr = 1、3、5、8、4、2、6、7、0、7、9

1 -> 3 -> 8(这是最短的路径)

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

基本思想是，您需要一个辅助结构，以帮助您跟踪最小路径。这些类型的结构通常被称为“后台指针”(在我们的例子中，您可以称它们为“前向指针”，因为我们正在前进，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()