0983. Minimum Cost For Tickets

题目信息

题号:

0983

难度:

Medium

主题:

旅行日期、通票覆盖、最小费用

原题:

LeetCode 0983

重点:

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。