使用列车线路的最小费用

Minimum Costs Using the Train Line

专题: Algorithmic Programming / 算法编程
难度: L4
来源: Citadel

个人笔记

题目详情

问题：使用列车线路的最小费用

考察：动态规划

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/minimum-costs-using-the-train-line/

英文原题

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 <= 10⁵
regular.length == n - 1
express.length == n - 1
1 <= regular[i], express[i] <= 10⁵

解析

思路：维护到每个站点时处于 regular 线和 express 线的最小成本。每一步可留在当前线，也可支付换线成本切到 express，再加对应边费用。

复杂度：时间 O(n)，空间 O(1) 或 O(n) 输出每站答案。

英文解析

Approach: Track two minimum costs at every station: arriving on the regular line and arriving on the express line. At each segment, either stay on the same line or pay the express transfer cost before taking the express segment.

Complexity: Time $O(n)$ , space $O(1)$ unless all station answers are stored.