diff options
Diffstat (limited to 'min_cost_ticket.py')
-rw-r--r-- | min_cost_ticket.py | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/min_cost_ticket.py b/min_cost_ticket.py new file mode 100644 index 0000000..02c00c1 --- /dev/null +++ b/min_cost_ticket.py @@ -0,0 +1,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] + ) + ) |