力扣题解 983

时间：2024-10-03 11:09:52

大家好，欢迎来到无限大的判断，祝大家国庆假期愉快

题目描述（中等）

最低票价
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

  • 一张 为期一天 的通行证售价为 costs[0] 美元；
  • 一张 为期七天 的通行证售价为 costs[1] 美元；
  • 一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

这道题是一个典型的动态规划问题，我们需要通过购买合理的火车票来最小化旅行的费用。对于给定的一组旅行天数 days 和各种票价 costs，我们要找到最低的总费用策略。
在这里插入图片描述

题目解析

输入/输出描述

  • 输入：

    • 一个整数数组 days 表示你需要旅行的天数。
    • 一个整数数组 costs，其中 costs[0] 是为期一天的票价，costs[1] 是为期七天的票价，costs[2] 是为期三十天的票价。

  • 输出：

    • 一个整数，即完成所有给定旅行天数所需的最低费用。
问题要求

对于需要旅行的每一天，我们有三种购买票的选择：一天，七天，或者三十天。我们要通过合理选择票种，在满足旅行需要的同时，使总花费最小。

解题思路

  1. 动态规划定义：

    • 设 dp[i] 表示从第 1 天到第 i 天的旅行最低费用。

  2. 转移方程：

    • 如果第 i 天没有安排旅行，那么 dp[i] = dp[i-1]。
    • 如果有旅行安排，dp[i] 可以从以下三种情况中得来：
      • 使用 1 天票：dp[i] = dp[i-1] + costs[0]
      • 使用 7 天票：dp[i] = dp[i-7] + costs[1]（这里注意如果 i < 7，则 dp[i-7] 可以看作 0）
      • 使用 30 天票：dp[i] = dp[i-30] + costs[2]（这里注意如果 i < 30，则 dp[i-30] 可以看作 0）
    • 我们选择三种情况中费用最低的方案：dp[i] = min(dp[i-1] + costs[0], dp[i-7] + costs[1], dp[i-30] + costs[2])

  3. 初始条件：

    • dp[0] = 0（第 0 天不需花费）

  4. 最终目标：

    • 求 dp[days[i]]，其中 i 是最大旅行日数，考虑只需处理在 days 中的天数。

C语言代码实现

#include <stdio.h>
#include <limits.h>

int mincostTickets(int* days, int daysSize, int* costs, int costsSize) {
    int dp[366] = {0};  // Using 366 because days range from 1 to 365
    
    int dayIndex = 0;
    
    for (int i = 1; i <= 365; i++) {
        if (dayIndex >= daysSize || i != days[dayIndex]) {
            dp[i] = dp[i - 1];
        } else {
            int oneDayPass = dp[i - 1] + costs[0];
            int sevenDayPass = dp[i - 7 > 0 ? i - 7 : 0] + costs[1];
            int thirtyDayPass = dp[i - 30 > 0 ? i - 30 : 0] + costs[2];
            
            dp[i] = fmin(oneDayPass, fmin(sevenDayPass, thirtyDayPass));
            dayIndex++;
        }
    }
    
    return dp[days[daysSize - 1]];
}

int main() {
    int days[] = {1, 4, 6, 7, 8, 20};
    int costs[] = {2, 7, 15};
    int result = mincostTickets(days, 6, costs, 3);
    printf("Minimum cost: %d\n", result);
    return 0;
}

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int mincostTickets(vector<int>& days, vector<int>& costs) {
    vector<int> dp(366, 0);
    
    int n = days.size();
    int dayIndex = 0;
    
    for (int i = 1; i <= 365; i++) {
        if (dayIndex >= n || i != days[dayIndex]) {
            dp[i] = dp[i - 1];
        } else {
            int oneDayPass = dp[i - 1] + costs[0];
            int sevenDayPass = dp[max(0, i - 7)] + costs[1];
            int thirtyDayPass = dp[max(0, i - 30)] + costs[2];
    
            dp[i] = min({oneDayPass, sevenDayPass, thirtyDayPass});
            dayIndex++;
        }
    }
    
    return dp[days[n - 1]];
}

int main() {
    vector<int> days = {1, 4, 6, 7, 8, 20};
    vector<int> costs = {2, 7, 15};
    int result = mincostTickets(days, costs);
    cout << "Minimum cost: " << result << endl;
    return 0;
}

算法分析

  • 时间复杂度：O(n)，其中 n 是 days 的大小，因为我们只遍历每一个旅行天数，并对其更新一次。
  • 空间复杂度：O(365)，主要用于 dp 数组的存储。
  • 该方案特别高效，因为对于每一个天数，我们只需决定三种选择中哪种最优，并且通过比较每次操作来更新 dp 的值。

结论

动态规划的关键在于将较大的问题划分为多个子问题，并从小到大不断求解。因此，通过合理地定义状态和状态转移方程，这个问题可以被有效解决。上述方案巧妙地利用了 dp 技巧，使得问题分析更为简洁，并能保证所需的最小费用。

相关文章