[983] 最低票价

动态规划

details

解题思路：

这是一个典型的动态规划问题。我们需要用动态规划的方式去考虑每一天最小的花费，递推方程中，选择的方式是买 1 天、7 天或者 30 天的票，取其中的最小值。

定义状态：设 dp[i] 为在第 i 天完成所有旅行的最低费用。
状态转移方程：如果某一天是旅行日，可以通过三种方式购买票：
- 购买 1 日票，则需要支付 dp[i - 1] + costs[0]
- 购买 7 日票，则需要支付 dp[i - 7] + costs[1]
- 购买 30 日票，则需要支付 dp[i - 30] + costs[2]
非旅行日当天的费用与前一天相同，即 dp[i] = dp[i - 1]。
边界条件：如果某天不在 days 数组中，说明不是旅行日，那么 dp[i] 不需要更新，保持与前一天相同。

代码实现（JavaScript）：

var mincostTickets = function (days, costs) {
    let maxDay = days.at(-1);
    let dp = new Array(maxDay + 1).fill(0);
    let daySet = new Set(days);

    for (let i = 1; i <= maxDay; i++) {
        if (!daySet.has(i)) {
            dp[i] = dp[i - 1];
        } else {
            dp[i] = Math.min(dp[Math.max(0, i - 1)] + costs[0], dp[Math.max(0, i - 7)] + costs[1], dp[Math.max(0, i - 30)] + costs[2]);
        }
    }

    return dp[maxDay];
};

复杂度分析：

时间复杂度: O(n)，其中 n 是 days 数组的长度。我们需要遍历每一天来更新 dp 数组。
空间复杂度: O(maxDay)，其中 maxDay 是旅行的最后一天，因为我们需要存储 dp 数组。

贪心算法

details

贪心算法思路：

对于每一个旅行日，我们需要做出决策：购买哪种票能够使得总费用最小。贪心的思路是从后往前贪心地选择最适合当前旅行日的票，依据当前的最远有效天数来判断选择哪种票更合适。

贪心策略：

从最后一天开始倒推，每次选择一种能涵盖最多天数且花费最少的票。
如果当前的旅行日落在某张票的有效期内，则跳到那张票的有效期结束后的下一天继续判断。
重复这一过程，直到处理完所有的旅行日。

贪心实现方式：

每次从第一个未覆盖的旅行日开始，分别计算使用 1 天票、7 天票和 30 天票所能覆盖的范围，并选择花费最少的一种票。
继续处理未被覆盖的旅行日，直到所有旅行日都被覆盖。

var mincostTickets = function (days, costs) {
    let n = days.length;
    let lastDay = days[n - 1];
    let idx = 0; // 指向当前的第一个旅行日
    let totalCost = 0;

    while (idx < n) {
        let nextIdx1 = idx; // 使用1天票后的下一天
        let nextIdx7 = idx; // 使用7天票后的下一天
        let nextIdx30 = idx; // 使用30天票后的下一天

        // 找到1天票，7天票，30天票有效期后的索引
        while (nextIdx1 < n && days[nextIdx1] <= days[idx] + 0) nextIdx1++;
        while (nextIdx7 < n && days[nextIdx7] <= days[idx] + 6) nextIdx7++;
        while (nextIdx30 < n && days[nextIdx30] <= days[idx] + 29) nextIdx30++;

        // 计算使用1天票、7天票、30天票分别的花费
        let cost1 = totalCost + costs[0];
        let cost7 = totalCost + costs[1];
        let cost30 = totalCost + costs[2];

        // 贪心选择花费最少的票并更新 idx
        if (cost1 <= cost7 && cost1 <= cost30) {
            totalCost = cost1;
            idx = nextIdx1;
        } else if (cost7 <= cost30) {
            totalCost = cost7;
            idx = nextIdx7;
        } else {
            totalCost = cost30;
            idx = nextIdx30;
        }
    }

    return totalCost;
};