871. Minimum Number of Refueling Stops

https://leetcode.com/problems/minimum-number-of-refueling-stops/

给定一系列加油站的位置和从该加油站加油后能跑多远，问在有startFule这么多的初始可跑里程，最少加几次油可到达target。题目和Jump Game II很像，都是元素值代表能跳多远，找最少跳的次数。因此用greedy或DP解。greedy维持一个当前的window代表这次能走的range，遍历window后找出window内路过的加油站最远能到哪，作为下一个window的边界。DP 根据加油站分成i个子问题，action为在i加或不加油，限制是能否到达i加油站。但如果用常规背包写法把限制encoding进j，让j作为里程看dp[i - 1][j - s[i]]，j的范围会非常大。需要换个思路，优化目标不作为dp元素值而是作为状态，并把限制放进值，即dp[i][j]存前i个加油站加j次油最远能到达的距离。

DP思路参考自花花。

/*
 * @lc app=leetcode id=871 lang=cpp
 *
 * [871] Minimum Number of Refueling Stops
 */

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