LeetCode: 871. Minimum Number of Refueling Stops

LeetCode: 871. Minimum Number of Refueling Stops

题目描述

A car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: 
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

Note:

1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

解题思路 —— 动态规划

dp[i] 为到达当前站点加气 i 次 的最大气量(包括已经用过的)。
若当前站点,没加气则,dp[i] = dp[i](后者是到达前一个站点加气 i 次的最大气量);
若当前站点加气,则,dp[i] = dp[i-1]+station[i][1]dp[i-1] 是到达前一个站点加气 i-1 次的最大气量)。

AC 代码

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        // dp[i]: 到达当前站,加油 i 次 的最大气量
        int dp[504]= { startFuel };
        stations.push_back({target, 0});

        for(int i = 1; i <= stations.size(); ++i)
        {
            dp[i] = -1;
        }

        for(size_t i = 0; i < stations.size(); ++i)
        {
            for(int j = i+1; j >= 0; --j)
            {
                int maxFuel = -1;
                // 第 i 站不加气
                if(dp[j] >= stations[i][0])
                {
                    maxFuel = max(maxFuel, dp[j]);
                }
                // 第 i 站加气
                if(j > 0 && dp[j-1] >= stations[i][0])
                {
                    maxFuel = max(maxFuel, dp[j-1] + stations[i][1]);
                }
                dp[j] = maxFuel;
            }
        }

        for(int i = 0; i <= stations.size(); ++i)
        {
            if(dp[i] != -1) return i;
        }

        return -1;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:39
在记录秋招的大魔王很...:别被忽悠了,我做了多年销售。我可以告诉你,这就是忽悠你的,销售一定要看底薪也要看提成两者不可缺一。提成是有业绩的时候才拿的到的,谁能保证一直有单状态都好。销售有时候很讲究运气的。底薪是你这个人这个岗位日常工作体现的价值。别小看底薪,你看那些跳槽去做经理主管的,底薪底一些,人家愿意去吗?所以那些说销售靠提成的纯属忽悠,除非他们的业务很容易成单。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务