在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行.在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出.火车票有三种不同的销售方式:
一张为期一天的通行证售价为 costs[0] 美元;
一张为期七天的通行证售价为 costs[1] 美元;
一张为期三十天的通行证售价为 costs[2] 美元.
返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费.
输出:11
例如,这里有一种购买通行证的方法,可以让你完成你的旅行计划:
你总共花了 $11,并完成了你计划的每一天旅行.
首先我们看一眼题目类型,基本就是搜索,贪心,dp了,再看一眼数据范围365,基本上是dp,暴搜会爆炸的.
如果第i天不需要出去旅行,既然不旅行,那么最优解就是尽量不花钱,所以 dp[i]=dp[i-1]
如果第i天需要出去旅行,那么有三种情况:
7天前买的票正好延续到今天,花费即为:dp[i]=dp[i-7]+costs[1]
30天前买的票正好延续到今天,花费为:dp[i]=dp[i-30]+costs[2]
那么既然是最小值,我们肯定要求出这三种情况里面最小的那个了.则:dp[i]=min(dp[i-1]+costs[0]dp[i-7]+costs[1]dp[i]=dp[i-30]+costs[2]),注意如果i减去的值小于0,则答案为0.