871. 最低加油次数

871. 最低加油次数

很好的题目，不管是动态规划还是最大堆。
最大堆

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
       int sum = startFuel;
       Queue<Integer> maxHeap = new PriorityQueue<>((e1,e2)->{
           return e2-e1;
       });
       int n = stations.length;
       int res =0;
       for(int i=0; i<n; i++){
           while(sum < stations[i][0]) {
               if(maxHeap.size() == 0) {
                   return -1;
               }
               sum += maxHeap.poll();
               res++;
           }
            maxHeap.add(stations[i][1]);
       }
        while(sum < target) {
            if(maxHeap.size() == 0) {
                   return -1;
            }
            sum += maxHeap.poll();
            res++;
        }
        return res;

    }
}

动态规划

 int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        if(startFuel>=target)
            return 0;
        int n=stations.size();
        //dp[i][j]为经过了i个加油站、加了j次油能跑的最远距离(当然0<=j<=i)
        //vector<vector<int>> dp(n+1,vector<int> (n+1,0));
        //用二维int dp数组会在提交时发现在一个测试案例中两根整型相加
        //超过了INT_MAX而溢出报错，故这里换用long
        //因不支持vector<vector<long>> dp(n+1,vector<int> (n+1,0)); 
        //故换用下面四行来实现
        long dp[n+1][n+1];  
        for(int i=0;i<n+1;++i)
            for(int j=0;j<n+1;++j)
                dp[i][j]=0; //dp数组初始化
        
        //开成n+1的长度是因为把起点视为第0个加油站：起始状态处理
        for(int i=0;i<n+1;++i)
            dp[i][0]=startFuel; //甭管经过了几个站，一次油也不加那最多跑的就是startFuel的距离
        
        for(int i=1;i<n+1;++i)
        {
            for(int j=1;j<=i;++j)
            {
                if(dp[i-1][j]>=stations[i-1][0])  //在第i站不加油
                    dp[i][j]=dp[i-1][j];
                if(dp[i-1][j-1]>=stations[i-1][0]) //在第i站加油
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+stations[i-1][1]); //加油与否两种情况取大者
            }
        }

        for(int j=0;j<=n;++j)
            if(dp[n][j]>=target)
                return j;
        return -1;
    }