Minimum Cost for Tickets: A Dynamic Programming Approach

The problem asks us to find the minimum cost to cover given travel days using three types of tickets: 1-day, 7-day, and 30-day passes with their respective costs.

Analysis

This is a classic dynamic programming problem. We need to figure out the recurrence relation first. If we buy a ticket on day N, the total cost can be split into three cases:

1. Yesterday we bought today’s ticket (1-day pass)
2. Seven days ago we bought a 7-day pass that covers today
3. Thirty days ago we bought a 30-day pass that covers today

We just need to ensure all costs start from zero initially.

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
         dp.insert({-30, 0});
        for(int d : days)
            dp[d]=min({costs[0]+cost(d-1), costs[1]+cost(d-7), costs[2]+cost(d-30)});
        return dp.rbegin()->second;
    }
    
    int cost(int d) {
        return prev(dp.upper_bound(d))->second;
    }
    map<int, int> dp;
};

Key Insights

• This deepens understanding of DP concepts
• Using a map as a DP array is uncommon but effective. When N values are not continuous, it saves more space than allocating a large array
• STL functions greatly reduce code volume

#DP