每日一题|871. 最低加油次数|动态规划、内层逆序遍历

题目分析：找到第一个能够实现当前油量能够行驶的最大距离大于等于目标距离，且加油次数最小的加油站和加油次数。

每次加油之后能够行驶的最大距离都是由上一次加油的距离决定的，因此使用dp。

1、dp数组定义

dp[i]是一个一维数组，表示加油i次后，能够行驶的最大距离。

2、dp数组递推

更新的目的：找到当前加油次数能够行驶的最大距离。

当遍历到加油站 stations[i] 时，假设在到达该加油站之前已经加油 j 次，其中 0≤j≤i，则只有当 dp[j]≥stations[i][0] 时才能在加油 j 次的情况下到达加油站 stations[i] 的位置，这是dp更新的条件。 

在加油站stations[i] 加油之后，共加油 j+1 次，可以行驶的英里数是 dp[j]+stations[i][1]。遍历满足 0≤j≤i 且 dp[j]≥stations[i][0] 的每个下标 j，计算 dp[j+1] 的最大值。

dp[j + 1] = max(dp[j + 1], dp[j] + feul)

3、dp初始化

dp的最大长度表示最多加油的次数，也就是len(stations)。

dp是一个不断取最大值的过程，所有值初始化为0。

dp[0] = startFeul。

4、dp遍历顺序

外层i从小到大遍历全部的加油站，内层j从大到小遍历全部满足条件的加油次数，并更新dp。

为什么是从大到小遍历？

因为当前的dp都是以station[i]作为最后一站得到的，如果从小到大更新dp，将会重复计算feul的数量，得到一个当前i位置可以加油量的累计和，显然dp会越变越大。得到一个错误的结果。

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        dp = [startFuel] + [0] * len(stations)

        for i, (pos, fuel) in enumerate(stations):
            for j in range(i, -1, -1):
                if dp[j] >= pos:
                    dp[j+1] = max(dp[j+1], dp[j] + fuel)

        for i, dist in enumerate(dp):
            if dist >= target:
                return i
        return -1

原文地址：https://blog.csdn.net/m0_57527624/article/details/142742388

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！