[daily training] 871 Minimum refueling times

subject

The car set off from the starting point to the destination , The purpose is to the east of the starting position target Miles away .

There are gas stations along the way , Every station[i] For a gas station , It's east of the starting point station[i][0] Miles away , And there are station[i][1] A litre of petrol .

Suppose the capacity of the car's fuel tank is infinite , At first there was startFuel Liter fuel . Every time it drives 1 Miles will be used 1 A litre of petrol .

When the car arrives at the gas station , It may stop to refuel , Transfer all gasoline from the gas station to the car .

In order to reach the destination , What's the minimum number of refuels necessary for a car ？ If you can't get to your destination , Then return to -1 .

Be careful ： If the remaining fuel when the car arrives at the gas station is 0, It can still refuel there . If the remaining fuel is 0, Still think it has reached its destination .

Example 1：
Input ：target = 1, startFuel = 1, stations = []
Output ：0
explain ： We can get to our destination without refueling .

Example 2：
Input ：target = 100, startFuel = 1, stations = [[10,100]]
Output ：-1
explain ： We can't get to our destination , Not even getting to the first gas station .

Example 3：
Input ：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output ：2
explain ：
We set out with 10 Liter fuel .
We drove to the starting point 10 The gas station at mile , Consume 10 Liter fuel . Take the gas from 0 To add to 60 l .
then , We from 10 The gas station is miles away 60 The gas station at mile （ Consume 50 Liter fuel ）,
And take the gas from 10 To add to 50 l . Then we drove to our destination .
We are on the way 1 Two gas stations stop , So back 2 .

Tips ：
1 <= target, startFuel, stations[i][1] <= 10⁹
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < … < stations[stations.length-1][0] < target

Code

package dayLeetCode;

public class dayleetcoe871 {
    
    // dp dp[i] It means refueling i The maximum number of miles traveled 
    //  Take the oil away , Whether you use it or not depends on the specific situation , Always get the biggest oil 
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
    
        long[] dp = new long[stations.length + 1];
        dp[0] = startFuel;

        for (int i = 0; i < stations.length; i++){
    
            //  Before judgment j Can I get there with this refueling i,  If it can be reached, it will be judged whether it will be i Fill the car with gas from a gas station 
            for (int j = i; j >= 0; j--){
    
                if (dp[j] >= stations[i][0]){
    
                    dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
                }
            }
        }
        //  Find the least number of refuelling 
        for (int i = 0; i <= stations.length; i++){
    
            if (dp[i] >= target){
    
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
    
        dayleetcoe871 obj = new dayleetcoe871();
        System.out.println(obj.minRefuelStops(1, 1, new int[][]{
    }));
    }
}