LeetCode 871. 最低加油次数***

具体思路：

简单贪心最远距离不太行，因为会存在把可达路径跳过去的问题；

不过看题解可以简单贪心最多油量，而不是最远距离；

明天脑子清醒了再补充；

现在用的是二维多状态DP；

具体代码：

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n=stations.size();
        vector<vector<long long>>dp(n+1,vector<long long>(n+1,0));
        for(int i=0;i<=n;i++){
            dp[i][0]=startFuel;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dp[i-1][j]>=stations[i-1][0]){
                    //在本届点不加油；
                    dp[i][j]=dp[i-1][j];
                }
                if(dp[i-1][j-1]>=stations[i-1][0]){
                    //在本本节点加油；
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+stations[i-1][1]);
                }
            }
        }
        for(int i=0;i<=n;i++){
            if(dp[n][i]>=target)
                return i;
        }
        return -1;
    }
};