983. Minimum Cost For Tickets

[zeikar]

Problem link

https://leetcode.com/problems/minimum-cost-for-tickets

Problem Summary

1일권, 7일권, 30일권 티켓 가격이 주어지고 각 티켓을 사용해 주어진 날짜를 모두 여행할 수 있는 최소한의 비용을 구하는 문제.

Solution

간단한 DP 문제이다.
dp[i] = i일부터 여행할 수 있는 최소 비용으로 두면 현재 날짜부터 1일권, 7일권, 30일권을 썼을 때 비용 중 가장 작은 것으로 계속 더해 나가면 된다.

Source Code

from functools import cache
from typing import List


class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        @cache
        def solve(index: int):
            if index >= len(days):
                return 0

            # 1-day
            ret = solve(index + 1) + costs[0]

            # 7-day
            nextIndex = index + 1
            while nextIndex < len(days) and days[nextIndex] < days[index] + 7:
                nextIndex += 1

            ret = min(ret, solve(nextIndex) + costs[1])

            # 30-day
            while nextIndex < len(days) and days[nextIndex] < days[index] + 30:
                nextIndex += 1

            ret = min(ret, solve(nextIndex) + costs[2])
            return ret

        return solve(0)