983. Minimum Cost For Tickets

[namespace-io]

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        unordered_set<int> s(days.begin(), days.end());
        vector<int> dp(366, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= days.back(); i++){
            if(s.find(i) == s.end()) dp[i] = dp[i-1];
            else dp[i] = min(min(dp[max(0, i-1)] + costs[0], dp[max(0,i-7)] + costs[1]), dp[max(0, i-30)] + costs[2]);
        }
        
        return dp[days.back()];
    }
};

class Solution {
public:
    int dfs(int i, int j, vector<int>& days, vector<int>& costs, vector<vector<int>>& dp){
        if(dp[i][j] == INT_MAX){
            if(days[j] - days[i] + 1 <= 30) dp[i][j] = min(dp[i][j], costs[2]);
            if(days[j] - days[i] + 1 <= 7 ) dp[i][j] = min(dp[i][j], costs[1]);
            if(days[j] - days[i] + 1 <= 1 ) dp[i][j] = min(dp[i][j], costs[0]);
            for(int k = i; k < j; k++){
                dp[i][j] = min(dp[i][j], dfs(i, k, days, costs, dp) + dfs(k+1, j, days, costs, dp));
            }
        }
        
        return dp[i][j];
    }
    
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        return dfs(0, n-1, days, costs, dp);
    }
};