力扣题解 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),其中 ndays 的大小,因为我们只遍历每一个旅行天数,并对其更新一次。
  • 空间复杂度:O(365),主要用于 dp 数组的存储。
  • 该方案特别高效,因为对于每一个天数,我们只需决定三种选择中哪种最优,并且通过比较每次操作来更新 dp 的值。

结论

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