983. Minimum Cost For Tickets

2019-05-11 | 阅读：次

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

a 1-day pass is sold for costs[0] dollars;
a 7-day pass is sold for costs[1] dollars;
a 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

在一个受火车旅行欢迎的国家，您计划提前一年旅行一些火车。您将要旅行的一年中的几天作为阵列日。每天是1到365之间的整数。

火车票以3种不同的方式出售：

以1美元的成本出售1天通行证;
售出7天的通行证，费用为1美元;
售出30天的通行证，费用为[2]美元。

通行证允许连续多日旅行。例如，如果我们在第2天获得7天通行证，那么我们可以旅行7天：第2,3,4,5,6,7和8天。

在给定的天数列表中，每天返回您需要旅行的最少数量的美元。

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.
输入：天= [1,4,6,7,8,20]，费用= [2,7,15]
产量：11
说明：
例如，这里有一种购买通行证的方式，可以让您旅行计划：
在第1天，您购买了1天的通行证，费用为[0] = 2美元，涵盖第1天。
在第3天，您购买了7天的通行证，费用为[1] = 7美元，其中包括第3天，第4天，第9天。
在第20天，您购买了1天的通行证，费用为[0] = 2美元，涵盖第20天。
总共花了11美元，并涵盖了旅行的所有日子。

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.
输入：天= [1,2,3,4,5,6,7,8,9,10,30,31]，费用= [2,7,15]
产量：17
说明：
例如，这里有一种购买通行证的方式，可以让您旅行计划：
在第1天，您购买了30天的通行证，费用为[2] = 15美元，涵盖第1,2天，......，30天。
在第31天，您购买了1天的通行证，费用为[0] = 2美元，涵盖第31天。
总共花了17美元，涵盖了旅行的所有日子。

Note:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

python实践：

#!/usr/bin/env python
# _*_ coding:utf-8 _*_

class Solution:
    def mincostTickets(self, days, costs):
        # dp: 表示旅行到第i天为止， 所需要的最少的旅行价格
        dp = [0] * (days[-1]+1)
        if days[-1] < 8:
            for i in range(1, days[-1]):
                dp[i] = min(dp[i - 1] + costs[0], costs[1])
        elif days[-1]>=8 and days[-1] <= 30:
            for i in range(1, 8):
                dp[i] = min(dp[i-1] + costs[0], costs[1])
            for i in range(8, days[-1]):
                dp[i] = min(dp[i-1]+costs[0], dp[i-7]+costs[1], costs[2])
        else:
            for i in range(1, 8):
                dp[i] = min(dp[i-1] + costs[0], costs[1])
            for i in range(8, 31):
                dp[i] = min(dp[i-1]+costs[0], dp[i-7]+costs[1], costs[2])
            for i in range(31, days[-1]+1):
                dp[i] = min(dp[i-1]+costs[0], dp[i-7]+costs[1], dp[i-30]+costs[2])
        print(dp)
        return dp[-1]



if __name__ == '__main__':
    days = [1,4,6,7,8,20]
    costs = [2, 7, 15]
    t = Solution().mincostTickets(days, costs)
    print(t)
   
============================================
此方法不可行

stone

Linxia Yao

983. Minimum Cost For Tickets

python实践：