2361. Minimum Costs Using the Train Line π
Description
A train line going through a city has two routes, the regular route and the express route. Both routes go through the same n + 1
stops labeled from 0
to n
. Initially, you start on the regular route at stop 0
.
You are given two 1-indexed integer arrays regular
and express
, both of length n
. regular[i]
describes the cost it takes to go from stop i - 1
to stop i
using the regular route, and express[i]
describes the cost it takes to go from stop i - 1
to stop i
using the express route.
You are also given an integer expressCost
which represents the cost to transfer from the regular route to the express route.
Note that:
- There is no cost to transfer from the express route back to the regular route.
- You pay
expressCost
every time you transfer from the regular route to the express route. - There is no extra cost to stay on the express route.
Return a 1-indexed array costs
of length n
, where costs[i]
is the minimum cost to reach stop i
from stop 0
.
Note that a stop can be counted as reached from either route.
Example 1:
Input: regular = [1,6,9,5], express = [5,2,3,10], expressCost = 8 Output: [1,7,14,19] Explanation: The diagram above shows how to reach stop 4 from stop 0 with minimum cost. - Take the regular route from stop 0 to stop 1, costing 1. - Take the express route from stop 1 to stop 2, costing 8 + 2 = 10. - Take the express route from stop 2 to stop 3, costing 3. - Take the regular route from stop 3 to stop 4, costing 5. The total cost is 1 + 10 + 3 + 5 = 19. Note that a different route could be taken to reach the other stops with minimum cost.
Example 2:
Input: regular = [11,5,13], express = [7,10,6], expressCost = 3 Output: [10,15,24] Explanation: The diagram above shows how to reach stop 3 from stop 0 with minimum cost. - Take the express route from stop 0 to stop 1, costing 3 + 7 = 10. - Take the regular route from stop 1 to stop 2, costing 5. - Take the express route from stop 2 to stop 3, costing 3 + 6 = 9. The total cost is 10 + 5 + 9 = 24. Note that the expressCost is paid again to transfer back to the express route.
Constraints:
n == regular.length == express.length
1 <= n <= 105
1 <= regular[i], express[i], expressCost <= 105
Solutions
Solution 1: Dynamic Programming
We define $f[i]$ as the minimum cost from station $0$ to station $i$ when arriving at station $i$ by the regular route, and $g[i]$ as the minimum cost from station $0$ to station $i$ when arriving at station $i$ by the express route. Initially, $f[0]=0, g[0]=\infty$.
Next, we consider how to transition the states of $f[i]$ and $g[i]$.
If we arrive at station $i$ by the regular route, we can either come from station $i-1$ by the regular route or switch from the express route at station $i-1$ to the regular route. Therefore, we can get the state transition equation:
$$ f[i]=\min{f[i-1]+a_i, g[i-1]+a_i} $$
where $a_i$ represents the cost of taking the regular route from station $i-1$ to station $i$.
If we arrive at station $i$ by the express route, we can either switch from the regular route at station $i-1$ to the express route or continue on the express route from station $i-1$. Therefore, we can get the state transition equation:
$$ g[i]=\min{f[i-1]+expressCost+b_i, g[i-1]+b_i} $$
where $b_i$ represents the cost of taking the express route from station $i-1$ to station $i$.
We denote the answer array as $cost$, where $cost[i]$ represents the minimum cost from station $0$ to station $i$. Since we can reach station $i$ from any route, we have $cost[i]=\min{f[i], g[i]}$.
Finally, we return $cost$.
The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the number of stations.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
We notice that in the state transition equations of $f[i]$ and $g[i]$, we only need to use $f[i-1]$ and $g[i-1]$. Therefore, we can use two variables $f$ and $g$ to record the values of $f[i-1]$ and $g[i-1]$ respectively. This allows us to optimize the space complexity to $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|