aboutsummaryrefslogtreecommitdiff
path: root/min_cost_ticket.py
blob: 02c00c1872c2b597339ee9382198edf18ea34ee6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 983. Minimum Cost For Tickets

"""
you have planned some train traveling one year in advance. the days of the
year in which you will travel are given as an integer array 'days'. each day
is an integer 1 - 365. train tickets are sold in three different ways: 1 day
pass sold for 'costs[0]' dollars 7 day pass sold for 'costs[1]' dollars 30
day pass sold for 'costs[2]' dollars the passes allow that many days of
consecutive travel. return mininum number of dollars you need to travel every
day in the given list of days.
"""


class Solution(object):
    def mincostTickets(self, days, costs):
        """
        :type days: List[int]
        :type costs: List[int]
        :rtype: int
        """
        dp = [0 for i in range(days[-1] + 1)]
        dy = set(days)
        for i in range(days[-1] + 1):
            if i not in dy:
                dp[i] = dp[i - 1]
            else:
                dp[i] = min(
                    dp[max(0, i - 7)] + costs[1],
                    dp[max(0, i - 1)] + costs[0],
                    dp[max(0, i - 30)] + costs[2],
                )
        return dp[-1]


if __name__ == "__main__":
    obj = Solution()
    print(obj.mincostTickets(days=[1, 4, 6, 7, 8, 20], costs=[2, 7, 15]))
    print(
        obj.mincostTickets(
            days=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], costs=[2, 7, 15]
        )
    )