当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.983.Minimum Cost For Tickets 最低票价

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


上一篇 LeetCode.221.Maximal Square 最大正方形

下一篇 LeetCode.098.Validate Binary Search Tree 验证二叉搜索树BST

阅读
评论
1,584
阅读预计6分钟
创建日期 2020-05-06
修改日期 2020-05-06
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论