0983. Minimum Cost For Tickets¶
题目信息¶
- 题号:
0983
- 难度:
Medium
- 主题:
旅行日期、通票覆盖、最小费用
- 原题:
- 重点:
days是一年内严格递增的出行日;可购买连续覆盖 1、7 或 30 天的通票,必须覆盖每个出行日并最小化总费用
题目重述¶
给定严格递增的出行日期数组 days,日期范围为一年中的第 1 至 365 天;另给定数组 costs,依次表示 1 天、7 天和 30 天通票的价格。
在某天购买持续 d 天的通票后,它覆盖从购买当天开始的连续 d 个日历日。可以购买任意数量和类型的通票,并允许覆盖没有出行的日期。请返回确保 days 中每个出行日都有有效通票所需的最小总费用。
1 <= days.length <= 365,日期互不相同且严格递增;costs.length == 3,1 <= costs[i] <= 1000。
自建示例¶
两组相隔较远的连续出行:
输入:days = [1,2,8,9], costs = [3,8,20]
输出:12
解释:分别为四个出行日购买 1 天通票,总费用为 4 * 3 = 12。使用 7 天通票也无法把两组日期同时覆盖得更便宜。
只有一个出行日但七天票更便宜:
输入:days = [100], costs = [5,3,20]
输出:3
解释:虽然只需覆盖一天,但允许购买任意类型通票;7 天票价格 3 低于 1 天票价格 5,因此最小费用为 3。