难度: Hard
Submission
运行时间: 348 ms
内存: 40.4 MB
class Solution:
def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:
n = len(regular)
ans = [inf] * n
reg = [0] + [inf] * n
exp = [expressCost] + [inf] * n
for i in range(n):
reg[i+1] = reg[i] + regular[i]
exp[i+1] = min(exp[i] + express[i], reg[i+1] + expressCost)
ans[i] = min(reg[i+1], exp[i+1])
reg[i+1] = ans[i]
return ans
Explain
该题解采用动态规划的方式来解决乘坐火车路线的最少费用问题。它定义了两个数组reg和exp，分别用来记录到达每一站点时仅通过常规路线和通过快速路线累积的最小费用。此外，使用ans数组来存储到达每一站的总体最小费用。对于每一站点i，更新reg[i+1]为从上一站通过常规路线到达当前站的费用；exp[i+1]则是比较继续使用快速路线或者从常规路线转换到快速路线的费用，取较小值。最终，ans数组中存储的每个元素即为到达相应站点的最小费用。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:
n = len(regular) # 站点数量
ans = [inf] * n # 初始化答案数组，存储到达每个站点的最小费用
reg = [0] + [inf] * n # 初始化常规路线费用数组，第一站费用为0
exp = [expressCost] + [inf] * n # 初始化快速路线费用数组，第一站费用为expressCost
for i in range(n): # 遍历每个站点
reg[i+1] = reg[i] + regular[i] # 更新通过常规路线到达下一站的费用
exp[i+1] = min(exp[i] + express[i], reg[i+1] + expressCost) # 更新通过快速路线到达下一站的费用
ans[i] = min(reg[i+1], exp[i+1]) # 计算到达当前站的最小费用
reg[i+1] = ans[i] # 同步更新常规路线费用数组，以反映到达该站的最小费用
return ans # 返回计算好的每站的最小费用数组
Explore
在动态规划中维护常规路线和快速路线的费用数组可以帮助分别追踪两种不同的出行方式（常规和快速）到达每个站点的最小费用。这种方法的好处在于它允许我们在每个站点做出最优的决策，即选择当前站点到达成本最低的路线。此外，这种分离的管理方式简化了逻辑，使得更新每个站点的费用时更加直观和容易理解，能够清楚地比较继续当前路线或者切换到另一条路线的成本。
在更新快速路线费用时考虑从常规路线转换到快速路线的费用是因为，可能存在从常规路线转到快速路线在某些情况下能够降低总体的旅行成本。这种情况发生在常规路线到达某站后，加上额外的快速路线转换费用（expressCost）后，仍然比继续使用快速路线更经济。这种策略确保了在每一步都能选择成本最低的方案，从而达到整体成本最小化。
在动态规划中，`ans`数组确保每个站点费用最小的方法是在每个站点计算并存储通过常规路线和快速路线达到该站的最小费用。具体来说，每次更新站点i时，`ans[i]`会被设置为`reg[i+1]`（通过常规路线到达下一站的费用）和`exp[i+1]`（通过快速路线到达下一站的费用）之间的较小值。由于这种每步的最小化，`ans`数组最终反映了到达每个站点的最低可能费用。
在实现中，数组`reg`, `exp`, 和`ans`的初始值设置为`inf`（无穷大）具有特别的重要性，因为它代表着一个非常高的初始成本，确保在开始的比较过程中任何实际的费用都会被认为较小。这种设置有助于在动态规划过程中正确地更新这些数组，确保只有当找到更小的费用时，才会更新到达某站的成本。`inf`作为初始值也避免了对特定条件的额外检查，如未访问或不可达的状态。