贪心算法的汽车加油问题（列表索引超出范围）

我有一个小问题，使用贪心算法解决汽车加油问题。

问题介绍

您将前往距离您的家乡 ???? 英里远的另一个城市。你的车可以行驶 满箱油最多可行驶 ???? 英里，并且您从满箱油开始。沿途，距离您所在城市 stop1、stop2、...、stopN 处有加油站。最少需要补充多少次？

Input:

950
400
4
200 375 550 750

Output:

2

到目前为止我已经尝试过的

def car_fueling(dist,miles,n,gas_stations):
  num_refill, curr_refill, last_refill = 0,0,0
  while curr_refill <= n:
    last_refill = curr_refill
    while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    if curr_refill == last_refill:  
      return -1
    if curr_refill <= n:
      num_refill += 1
  return num_refill

我面临的问题是什么

在声明中

while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles)

我收到错误IndexError: list index out of range。正是因为gas_stations[curr_refill + 1]。所以当我尝试将其分离为while循环和一个if声明如

while (curr_refill <= n-1):
    if (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    else:
        break

它正在进入无限循环。

您能指出我面临的错误吗？

几个问题：

• &不是布尔与运算符。使用and
• curr_refill + 1 can be n，从而产生您得到的错误。注意后面的距离last加油站可以使用确定dist
• 的价值last_refill从一开始就是错误的：您尚未在 0 号站重新加油，因此不应将其初始化为 0。而是使用另一个代表您当前可以行驶多远的变量。

更正后的代码：

def car_fueling(dist,miles,n,gas_stations):
    num_refill, curr_refill, limit = 0,0,miles
    while limit < dist:  # While the destination cannot be reached with current fuel
        if curr_refill >= n or gas_stations[curr_refill] > limit:
            # Cannot reach the destination nor the next gas station
            return -1
        # Find the furthest gas station we can reach
        while curr_refill < n-1 and gas_stations[curr_refill+1] <= limit:
            curr_refill += 1
        num_refill += 1  # Stop to tank
        limit = gas_stations[curr_refill] + miles  # Fill up the tank 
        curr_refill += 1
    return num_refill

# Test cases
print(car_fueling(950, 400, 4, [200, 375, 550, 750]))  # 2
print(car_fueling(10, 3, 4, [1, 2, 5, 9]))  # -1