列表

详情

2361. 乘坐火车路线的最少费用

城市中的火车有两条路线，分别是常规路线和特快路线。两条路线经过 相同 的 n + 1 个车站，车站编号从 0 到 n。初始时，你位于车站 0 的常规路线。

给你两个 下标从 1 开始 、长度均为 n 的两个整数数组 regular 和 express ，其中 regular[i] 表示乘坐常规路线从车站 i - 1 到车站 i 的费用，express[i] 表示乘坐特快路线从车站 i - 1 到车站 i 的费用。

另外给你一个整数 expressCost，表示从常规路线转换到特快路线的费用。

注意：

返回 下标从 1 开始 、长度为 n 的数组 costs，其中 costs[i] 是从车站 0 到车站 i 的最少费用。

注意：每个车站都可以从任意一条路线 到达 。

 

示例 1：

输入：regular = [1,6,9,5], express = [5,2,3,10], expressCost = 8
输出：[1,7,14,19]
解释：上图展示了从车站 0 到车站 4 的最少费用方法。
- 乘坐常规路线从车站 0 到车站 1，费用是 1。
- 乘坐特快路线从车站 1 到车站 2，费用是 8 + 2 = 10。
- 乘坐特快路线从车站 2 到车站 3，费用是 3。
- 乘坐特快路线从车站 3 到车站 4，费用是 5。
总费用是 1 + 10 + 3 + 5 + 19。
注意到达其他车站的最少费用方法可以选择不同的路线。

示例 2：

输入：regular = [11,5,13], express = [7,10,6], expressCost = 3
输出：[10,15,24]
解释：上图展示了从车站 0 到车站 3 的最少费用方法。
- 乘坐特快路线从车站 0 到车站 1，费用是 3 + 7 = 10。
- 乘坐常规路线从车站 1 到车站 2，费用是 5。
- 乘坐特快路线从车站 2 到车站 3，费用是 3 + 6 = 9。
总费用是 10 + 5 + 9 = 24。
注意转换回特快路线时需要再次支付 expressCost 的费用。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<long long> minimumCosts(vector<int>& regular, vector<int>& express, int expressCost) { } };

cpp 解法, 执行用时: 236 ms, 内存消耗: 135.2 MB, 提交时间: 2023-10-16 23:18:28 

class Solution {
public:
    vector<long long> minimumCosts(vector<int>& regular, vector<int>& express, int expressCost) {
        int n = regular.size();
        vector<vector<long long>> dp (n + 1, vector<long long> (2, LLONG_MAX));
        vector<long long> ans(n);
        dp[0][0] = 0, dp[0][1] = expressCost;
        for (int i = 0; i < n; i++) {
            dp[i + 1][0] = min(dp[i][0], dp[i][1]) + regular[i];
            dp[i + 1][1] = min(dp[i][1], dp[i][0] + expressCost) + express[i];
            ans[i] = min(dp[i + 1][0], dp[i + 1][1]);
        }
        return ans;
    }
};

python3 解法, 执行用时: 388 ms, 内存消耗: 35.9 MB, 提交时间: 2023-10-16 23:17:38 

class Solution:
    def minimumCosts1(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:
        a, b, res = 0, expressCost, []
        for i, j in zip(regular, express):
            a, b = a + i, b + j
            if a > b: a = b
            elif b > a + expressCost: b = a + expressCost
            res.append(min(a,b))
        return res
        

    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:
        a, b, res = 0, expressCost, []
        for i, j in zip(regular, express):
            a, b = min(a + i, b + j), min(b + j, a + i + expressCost)
            res.append(min(a,b))
        return res

python3 解法, 执行用时: 1124 ms, 内存消耗: 52.9 MB, 提交时间: 2023-10-16 23:16:56 

class Solution:
    def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:
        n = len(regular)
        dp = [[float('inf') for _ in range(2)] for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(1,n + 1):
            for j in range(2):
                if dp[i - 1][j] == float('inf'):
                    continue
                for k in range(2):
                    if j == 0:
                        if k == 1:
                            dp[i][k] = min(dp[i][k],dp[i - 1][j] + expressCost + express[i - 1])
                        else:
                            dp[i][k] = min(dp[i][k],dp[i - 1][j] + regular[i - 1])
                    else:
                        if k == 1:
                            dp[i][k] = min(dp[i][k],dp[i - 1][j] + express[i - 1])
                        else:
                            dp[i][k] = min(dp[i][k],dp[i - 1][j] + regular[i - 1])
        ans = []
        for i in range(1,n + 1):
            ans.append(min(dp[i][0],dp[i][1]))
        return ans

java 解法, 执行用时: 8 ms, 内存消耗: 61.9 MB, 提交时间: 2023-10-16 23:16:25 

class Solution {
    /**
     * dp[i][0] 表示从车站 0 的常规路线到车站 i 的常规路线的最少费用，
     * dp[i][1] 表示从车站 0 的常规路线到车站 i 的特快路线的最少费用。
     */
    public long[] minimumCosts1(int[] regular, int[] express, int expressCost) {
        int n = regular.length;
        long[] costs = new long[n];
        long[][] dp = new long[n + 1][2];
        dp[0][0] = 0;
        dp[0][1] = expressCost;
        for (int i = 0; i < n; i++) {
            dp[i + 1][0] = Math.min(dp[i][0] + regular[i], dp[i][1] + Math.min(regular[i], express[i]));
            dp[i + 1][1] = Math.min(dp[i][0] + expressCost, dp[i][1]) + express[i];
            costs[i] = Math.min(dp[i + 1][0], dp[i + 1][1]);
        }
        return costs;
    }

    public long[] minimumCosts(int[] regular, int[] express, int expressCost) {
        int n = regular.length;
        long[] costs = new long[n];
        long dp0 = 0, dp1 = expressCost;
        for (int i = 0; i < n; i++) {
            long dp0New = Math.min(dp0 + regular[i], dp1 + Math.min(regular[i], express[i]));
            long dp1New = Math.min(dp0 + expressCost, dp1) + express[i];
            dp0 = dp0New;
            dp1 = dp1New;
            costs[i] = Math.min(dp0, dp1);
        }
        return costs;
    }
}

上一题

© 2024 leetcode.cn