LeetCode.983.Minimum Cost For Tickets 最低票价

题目描述

983 Minimum Cost For Tickets
https://leetcode-cn.com/problems/minimum-cost-for-tickets/

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

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

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

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

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

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。
你总共花了 $17，并完成了你计划的每一天旅行。

提示：
1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

---

解题过程

买 1日票 只管1天，买 7日票 能管今后的7天，买 30 日票能管今后的30天
所以我们在第 days[i] 天做买票的决策时，肯定要往后看，看 days[i] 之后的出行计划，假如后面连续好几天都要出行，肯定是买 多日票 更划算，最多往后看 30 天。
也就是，今天的决策依赖后续如何安排，即前面依赖后面，即后面的安排好了前面的就能定了，所以引出从后往前考虑的思路

dp[i] 表示能完成从第 days[i] 天开始到结束的最小花费
dp[] 数组长度为 days.length + 1，全部初始化为0
从后往前考虑，即做第 days[i] 天的买票决策 dp[i] 时， 从 days[i+1] 天开始的最小花费 dp[i+1] 已经确定。
对于第 days[i] 天，有三种买票方式：

1. 购买 1 日票只能管今天，总花费要加上从第 days[i] + 1 天开始的后续花费
2. 购买 7 日票能管从第 days[i] 天到 days[i] + 6 天，总花费要加上从第 days[i] + 7 天开始的后续花费
3. 购买 30 日票能管从第 days[i] 天到 days[i] + 29 天，总花费要加上从第 days[i] + 30 天开始的后续花费

我们取三种方案中总花费最小的，作为从当天即第 days[i] 天开始的花费 dp[i]

这里还有个问题，如何计算 从第 days[i] + n 天开始的后续花费？其中 n=1,7,30
举例，days=[1,4,6,7,8,20]， 假如当前 i = 0，即 days[i] 值为 1，即第 1 天，则

1. 购买 1 日票只能管今天，总花费要加上从第 2 天开始的后续花费，由于第 2 天不需要出行，后续花费是 i 之后第一个值大于等于 2 的元素（4）的 dp 值，即 dp[1]，表示从第 4 天开始的最小花费。
2. 购买 7 日票能管从第 1 天到 7 天，总花费要加上从第 8 天开始的后续花费，即 i 之后第一个值大于等于 8 的元素（8）的 dp 值，即 dp[4]，表示从第 8 天开始的最小花费。
3. 购买 30 日票能管从第 1 天到 30 天，总花费要加上从第 31 天开始的后续花费，即 i 之后第一个值大于等于 31 的元素（没有）的 dp 值，由于不存在取 dp[days.length] 的值，即 dp[6]，固定为 0，dp 数组长度比 days 多 1 为的就是兼容这种情况。

时间复杂度 O(n)，方法 findLeastIndexAfterN 复杂度为常数 O(1)，因为下标 j 最多移动 30 步
空间复杂度 O(n)

private static class SolutionV2020 {
    public int mincostTickets(int[] days, int[] costs) {
        // dp[i] 表示能完成从第 days[i] 天开始到结束的最小花费
        int[] dp = new int[days.length + 1]; // 全初始化为0
        // 从后往前考虑
        for (int i = days.length - 1; i >= 0; i--) {
            // 在第 days[i] 天购买 1日、7日、30日票的花费，取其中最小的
            // 购买 1 日票只能管今天，总花费要加上从第 days[i] + 1 天开始的后续花费
            int buy1DayCost = costs[0] + dp[i + 1];
            // 购买 7 日票能管从第 days[i] 天到 days[i] + 6 天，总花费要加上从第 days[i] + 7 天开始的后续花费
            int buy7DayCost = costs[1] + dp[findLeastIndexAfterN(days, i, days[i] + 7)];
            // 购买 30 日票能管从第 days[i] 天到 days[i] + 29 天，总花费要加上从第 days[i] + 30 天开始的后续花费
            int buy30DayCost = costs[2] + dp[findLeastIndexAfterN(days, i, days[i] + 30)];
            dp[i] = Math.min(buy1DayCost, Math.min(buy7DayCost, buy30DayCost));
        }
        return dp[0];
    }

    // 找到 days[] 数组中 i 之后第一个大于等于 target 的元素的下标，这个方法复杂度为常数 O(1)，因为下标 j 最多移动 30 步
    private int findLeastIndexAfterN(int[] days, int i, int target) {
        int j = i;
        while (j < days.length && days[j] < target) {
            j++;
        }
        return j;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_983_MinimumCostForTickets.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_983_MinimumCostForTickets.java

---