Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path is fixed (ie) you have to go from C1 to Cn through C2, C3,.. and so on. The objective is to fill fuel in these cities in such a way the spendings on fuel is minimized. I thought about storing the minimum prices within a window whose requirements add up to K and then find the minimum cost required to traverse. I’m not sure how it holds up or is it even right in the first place. What if being greedy and filling up fuel to reach the city empty till you reach the closest city with cheaper fuel, not the optimal solution? How do i prove that it is?