DSA Master Logo
DSAMaster
Sign InSign Up
mediumDynamic ProgrammingPattern: DP

Minimum Cost Circular Traversal with Refueling Solution

Problem Statement

You are given two arrays of positive integers: `travelExpenses`, where `travelExpenses[i]` is the amount of fuel consumed to travel from station `i` to station `(i+1) % n`; and `refuelCosts`, where `refuelCosts[i]` is the monetary cost to completely refuel your vehicle at station `i`. You also have an integer `maxCapacity` representing your vehicle's maximum fuel tank capacity. You start at station `0` with `0` fuel. Your objective is to traverse sequentially through all stations from `0` to `n-1` and finally return to station `0`. At each station `i`, before departing for station `(i+1) % n`, you have the option to fully refuel your tank to `maxCapacity` by paying `refuelCosts[i]`. You must always ensure you have enough fuel to complete the next leg of travel. Determine the minimum total monetary cost spent on refueling to complete the entire circular journey. If it's impossible to complete the journey under these conditions, return `-1`.

Examples

Example 1:
Input:travelExpenses = [5, 3, 4], refuelCosts = [10, 2, 8], maxCapacity = 8
Output:12
Explanation: Start at station 0 with 0 fuel. To travel to station 1 (cost 5), you must refuel at station 0 (cost 10). Fuel becomes 8. (Total cost = 10) Travel 0->1. Fuel becomes 3. Arrive at station 1. At station 1, you need 3 fuel to go to station 2. Current fuel (3) is sufficient. You have two options: 1. Don't refuel: Total cost = 10. Fuel becomes 3. Travel 1->2. Fuel becomes 0. Arrive at station 2. At station 2, you need 4 fuel to go to station 0. Current fuel (0) is insufficient. Must refuel (cost 8). Total cost = 10+8=18. Fuel becomes 8. Travel 2->0. Fuel becomes 4. Journey complete. 2. Refuel: Total cost = 10+2=12. Fuel becomes 8. Travel 1->2. Fuel becomes 5. Arrive at station 2. At station 2, you need 4 fuel to go to station 0. Current fuel (5) is sufficient. Don't refuel. Total cost = 12. Fuel becomes 5. Travel 2->0. Fuel becomes 1. Journey complete. The minimum cost is 12.
Example 2:
Input:travelExpenses = [10, 2], refuelCosts = [1, 1], maxCapacity = 5
Output:-1
Explanation: Start at station 0 with 0 fuel. To travel to station 1, you need 10 fuel. Even if you refuel at station 0, your tank capacity is only 5. Since 5 < 10, it's impossible to make the first leg of travel. Thus, the journey cannot be completed.

Constraints

  • `1 <= n <= 10^4`
  • `1 <= travelExpenses[i] <= 1000`
  • `1 <= refuelCosts[i] <= 1000`
  • `1 <= maxCapacity <= 1000`
  • `travelExpenses.length == refuelCosts.length == n`
Time: O(n^2 * maxCapacity) Space: O(n * maxCapacity)
The optimized approach uses dynamic programming to store the minimum cost to reach each station with a certain amount of fuel, considering the refueling options at each station. This approach has a time complexity of O(n^2 * maxCapacity) and a space complexity of O(n * maxCapacity), making it much more efficient than the brute force approach. By breaking down the problem into smaller subproblems and solving them only once, we can avoid redundant calculations and optimize the solution.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

import sys def minCost(travelExpenses, refuelCosts, maxCapacity): n = len(travelExpenses) dp = [float("inf")] * n dp[0] = 0 for i in range(n): for j in range(i + 1, n + i): totalFuel = 0 for k in range(i, j): totalFuel += travelExpenses[k % n] if totalFuel > maxCapacity: continue dp[j % n] = min(dp[j % n], dp[i] + refuelCosts[i]) if dp[0] == float("inf"): return -1 return dp[0] t = 1 for _ in range(t): n, maxCapacity = map(int, input().split()) travelExpenses = list(map(int, input().split())) refuelCosts = list(map(int, input().split())) print(minCost(travelExpenses, refuelCosts, maxCapacity))

Related Problems

Maximum Profit from Scheduled Deliveries
Dynamic Programming•medium
Longest Alternating Subsequence
Dynamic Programming•medium
Max Resource Allocation
Dynamic Programming•easy
Maximize Subset Points
Dynamic Programming•medium