Minimum Cost For Tickets
Let OPT(i, j) is the minimum cost you need to spend to travel from day i-th to day j-th.\nWe have 3 options to buy ticket at a day:\n Buy 1-day pass with the pr
Let OPT(i, j) is the minimum cost you need to spend to travel from day i-th to day j-th.\nWe have 3 options to buy ticket at a day:\n* Buy 1-day pass with the price costs[0]\n* Buy 7-day pass with the price costs[1]\n* Buy 30-day pass with the price costs[2]\n\nTherefore, we can set a target function as follow:\n```\nOPT(i, j) = min(costs[0] + OPT(i+1, j), \n                costs[1] + OPT(i+7, j), \n                costs[2] + OPT(i+30, j))\n```\n\nFrom this target function, we can easily to write python code as\n\n```\nimport bisect\nimport functools\nclass Solution:\n    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n        def find_next_day(start: int, no_of_days: int) -> int:\n            next_idx = bisect.bisect_left(days, days[start] + no_of_days)\n        \n            # print (f\'{next_idx} {days}\')\n        \n            if next_idx < len(days):\n                while next_idx - 1 >= 0 and days[next_idx] == days[next_idx - 1]:\n                    next_idx -= 1\n        \n            next_days = next_idx if next_idx < len(days) else -1\n            \n            return next_days\n        \n        @functools.lru_cache(maxsize=None)\n        def solve(start: int) -> int:\n            if start < 0 or start >= len(days):\n                return 0\n        \n            one_day = costs[0] + solve(start + 1 if start + 1 < len(days) else -1)\n        \n            next_days = find_next_day(start, 7)\n        \n            seven_days = costs[1] + solve(next_days) \n        \n            next_days = find_next_day(start, 30)\n        \n            thiry_days = costs[2] + solve(next_days) \n        \n            return min(one_day, seven_days, thiry_days)\n        \n        return solve(0)\n```
['Dynamic Programming', 'Python3']