MinimumCostForTickets.cpp

// Source : https://leetcode.com/problems/minimum-cost-for-tickets/
// Author : Hao Chen
// Date   : 2019-01-29

/***************************************************************************************************** 
 *
 * In a country popular for train travel, you have planned some train travelling one year in advance.  
 * The days of the year that you will travel is given as an array days.  Each day is an integer from 1 
 * to 365.
 * 
 * Train tickets are sold in 3 different ways:
 * 
 * 	a 1-day pass is sold for costs[0] dollars;
 * 	a 7-day pass is sold for costs[1] dollars;
 * 	a 30-day pass is sold for costs[2] dollars.
 * 
 * The passes allow that many days of consecutive travel.  For example, if we get a 7-day pass on day 
 * 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.
 * 
 * Return the minimum number of dollars you need to travel every day in the given list of days.
 * 
 * Example 1:
 * 
 * Input: days = [1,4,6,7,8,20], costs = [2,7,15]
 * Output: 11
 * Explanation: 
 * For example, here is one way to buy passes that lets you travel your travel plan:
 * On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
 * On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
 * On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
 * In total you spent $11 and covered all the days of your travel.
 * 
 * Example 2:
 * 
 * Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
 * Output: 17
 * Explanation: 
 * For example, here is one way to buy passes that lets you travel your travel plan:
 * On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
 * On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
 * In total you spent $17 and covered all the days of your travel.
 * 
 * Note:
 * 
 * 	1 <= days.length <= 365
 * 	1 <= days[i] <= 365
 * 	days is in strictly increasing order.
 * 	costs.length == 3
 * 	1 <= costs[i] <= 1000
 * 
 ******************************************************************************************************/

class Solution {
private:
    int min(int x, int y){
        return x < y ? x : y;
    }
    int min(int x, int y, int z) {
        return min(min(x, y), z);
    }
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {

        // Dynamic Programming
        vector<int> dp(days.size(), INT_MAX);

        // dp[i] is the minimal cost from Days[0] to Days[i]
        dp[0] = costs[0];

        for (int i = 1; i< days.size(); i ++) {

            // the currnet day need at least 1-day pass cost
            int OneDayPass = dp[i-1] + costs[0];

            // Seprating the array to two parts.
            //     days[0] -> days[j] -> day[i]
            //
            // calculate the day[i] - day[j] whether can use 7-day pass or 30-day pass
            //
            // Traking the minimal costs, then can have dp[i] minimal cost

            int SevenDayPass = INT_MAX, ThrityDayPass = INT_MAX;
            for (int j=i-1; j>=0; j--){
                if (days[i] - days[j] < 7 )  {
                    SevenDayPass  = dp[j-1] + costs[1];
                } else if (days[i] - days[j] < 30 ) {
                    ThrityDayPass = dp[j-1] + costs[2];
                } else {
                    break;
                }
                int m = min(OneDayPass, SevenDayPass, ThrityDayPass);
                if ( dp[i] > m )  dp[i] = m;
            }

        }

        return dp[dp.size()-1];
    }
};