Skip to main content

983. Minimum Cost For Tickets

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

Python​

Top Down DP​

from functools import cache
from math import inf


class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        durations = [1, 7, 30]

        @cache
        def dp(i):
            if i >= len(days):
                return 0

            ans = inf
            j = i
            for cost, duration in zip(costs, durations):
                while j < len(days) and days[j] < days[i]+duration:
                    j += 1
                ans = min(ans, dp(j)+cost)
            return ans

        return dp(0)

Javascript​

/**
 * @param {number[]} days
 * @param {number[]} costs
 * @return {number}
 */
var mincostTickets = function(days, costs) {
    const memo = {};
    const dp = (i) => {
        if (i === days.length) return 0;
        if (memo.hasOwnProperty(i)) return memo[i];
        
        let min = Infinity;
        const steps = [1,7,30];
        for (let j = 0; j < costs.length; j++) {
            const cost = costs[j];
            let k = i;
            while (k < days.length && days[k] < days[i] + steps[j]) {
                k++;
            }
            
            min = Math.min(min, cost + dp(k))
        }
        
        return memo[i] = min;
    }
    
    return dp(0);
};