Minimum costs using the train line

Array Dynamic Programming

77.9% acceptance

Mar 31, 2026

196

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_costs(regular: Vec<i32>, express: Vec<i32>, express_cost: i32) -> Vec<i64> {
    let n = regular.len();
    let mut costs = vec![0i64; n];
    let mut reg = 0i64;
    let mut exp = express_cost as i64;
    
    for i in 0..n {
      let new_reg = reg.min(exp) + regular[i] as i64;
      let new_exp = exp.min(reg + express_cost as i64) + express[i] as i64;
      reg = new_reg;
      exp = new_exp;
      costs[i] = reg.min(exp);
    }
    
    costs
  }
}