324.摆动排序II

链接：324.摆动排序II
难度：Medium
标签：贪心、数组、分治、快速选择、排序
简介：汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

题解 1 - cpp

• 编辑时间：2022-07-02
• 执行用时：92ms
• 内存消耗：15.8MB
• 编程语言：cpp
• 解法介绍：dp[i] = 当 i 为最后一个加油站时，最远能跑的公里数。

class Solution {
   public:
    int minRefuelStops(int target, int startFuel,
                       vector<vector<int>>& stations) {
        int n = stations.size();
        vector<long> dp(n + 1);
        dp[0] = startFuel;
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (dp[j] >= stations[i][0]) {
                    dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1]);
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            if (dp[i] >= target) return i;
        }
        return -1;
    }
};