1D DP

Leetcode 983. Minimum Cost For Tickets

Jimmy (xiaoke) Shen

·

Follow

1 min read

·

Aug 26, 2020

--

Listen

Share

983. Minimum Cost For Tickets

int memo[365];
class Solution {
public:
    int dp(vector<int>& days, vector<int>& costs, int i){
        if (i >= days.size()) return 0;
        if (i == days.size() - 1) return memo[i] = *min_element(costs.begin(), costs.end());
        if (memo[i] != -1) return memo[i];
        int this_ret = INT_MAX;
        
        //one day tickey
        int onedayCost = costs[0] + dp(days, costs, i + 1);
        
        
        // 7 days ticket
        int days_after7 = days[i] + 7;
        int j = lower_bound(days.begin(), days.end(), days_after7) - days.begin();
        int oneweekCost = costs[1] + dp(days, costs, j);
        
        // 30 days ticket
        int days_after30 = days[i] + 30;
        j = lower_bound(days.begin(), days.end(), days_after30) - days.begin();
        int onemonthCost = costs[2] + dp(days, costs, j);
        
        // aggregate to get the optimal result
        this_ret = min(this_ret, onedayCost);
        this_ret = min(this_ret, oneweekCost);
        this_ret = min(this_ret, onemonthCost);
        
        
        return memo[i] = this_ret;
    }
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        memset(memo, -1, sizeof(memo));
        return dp(days, costs, 0);
        
    }
};