1497. Minimum Number of Refueling Stops
int minimumNumberofRefuelingStops(int target, int startFuel, vector<vector<int>> &stations) {
// Write your code here.
//这题还是很难的，知道用DP，但不知道怎么定义state。想了想，怎么定义state都解释不通。
//还是解法思想，看了答案，定义state为停i次，油箱中一共加了多少油。
const int size = stations.size();
if(size == 0){
if(startFuel >= target){
return 0;
}
else{
return -1;
}
}
vector<long> dp(size + 1, startFuel);
dp[0] = startFuel;
for(int k = 0; k < size; k++){//这里顺序反了就不对了。k在外还是i在外？看实际逻辑吧，要在实际
//物理意义中找到答案
for(int i = 0; i <= k; i++){
if(dp[i] >= stations[k][0]){
dp[i + 1] = max(dp[i + 1], dp[i] + stations[k][1]);
}
}
}
for(int i = 0; i <= size; i++){
if(dp[i] >= target){
return i;
}
}
return -1;
}
Comments
Post a Comment