使用列车线路的最小费用

A train line has n stations numbered from 1 to n. You are given a 0-indexed array regular of length n - 1 where regular[i] is the cost to travel from station i + 1 to station i + 2. You are also given a 0-indexed array express of length n - 1 where express[i] is the cost to travel from station i + 1 to station i + 2 using the express line.

You can only use the express line at most once. Return the minimum cost to travel from station 1 to station n.

 

Example 1:

Input: regular = [1,5,6,9], express = [8,4,2,1]
Output: 15
Explanation:
One possible way to minimize the cost is to take the regular line from station 1 to station 3, the express line from station 3 to station 4, and the regular line from station 4 to station 5.
The total cost is regular[0] + regular[1] + express[2] + regular[3] = 1 + 5 + 2 + 9 = 17.
However, a better way is to take the express line from station 2 to station 3, and the regular line from station 1 to station 2 and from station 3 to station 5.
The total cost is regular[0] + express[1] + regular[2] + regular[3] = 1 + 4 + 6 + 9 = 20.
But the optimal way is to take the regular line from station 1 to station 2, the express line from station 2 to station 4, and the regular line from station 4 to station 5.
The total cost is regular[0] + express[1] + express[2] + regular[3] = 1 + 4 + 2 + 9 = 16.
But the optimal way is to take the regular line from station 1 to station 3, the express line from station 3 to station 5.
The total cost is regular[0] + regular[1] + express[2] + express[3] = 1 + 5 + 2 + 1 = 9.

Example 2:

Input: regular = [1,1,1,1], express = [9,9,9,9]
Output: 4
Explanation:
It is optimal to use the regular line from station 1 to station 5.

 

Constraints:

• 2 <= n <= 105
• regular.length == n - 1
• express.length == n - 1
• 1 <= regular[i], express[i] <= 105