Minimum Cost For Tickets Solutions in C++

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



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];
    }
};

/// Source : https://leetcode.com/problems/minimum-cost-for-tickets/
/// Author : liuyubobobo
/// Time   : 2019-01-28

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;


/// Memory Search - Day Variant
/// Time Complexity: O(365)
/// Space Complexity: O(len(days))
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {

        unordered_set<int> day_set;
        for(int day: days)
            day_set.insert(day);

        vector<int> dp(366, -1);
        return dfs(0, day_set, costs, dp);
    }

private:
    int dfs(int day, const unordered_set<int> day_set, const vector<int>& costs,
            vector<int>& dp){

        if(day > 365) return 0;
        if(dp[day] != -1) return dp[day];

        if(!day_set.count(day))
            return dp[day] = dfs(day + 1, day_set, costs, dp);

        int res = costs[0] + dfs(day + 1, day_set, costs, dp);
        res = min(res, costs[1] + dfs(day + 7, day_set, costs, dp));
        res = min(res, costs[2] + dfs(day + 30, day_set, costs, dp));

        return dp[day] = res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-cost-for-tickets/
/// Author : liuyubobobo
/// Time   : 2019-01-28

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;


/// Dynamic Programming - Day Variant
/// Time Complexity: O(365)
/// Space Complexity: O(len(days))
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {

        unordered_set<int> day_set;
        for(int day: days)
            day_set.insert(day);

        vector<int> dp(400, 0);
        dp[365] = day_set.count(365) ? costs[0] : 0;
        for(int day = 364; day >= 1; day --) {
            if (!day_set.count(day)) dp[day] = dp[day + 1];
            else{
                dp[day] = costs[0] + dp[day + 1];
                dp[day] = min(dp[day], costs[1] + dp[day + 7]);
                dp[day] = min(dp[day], costs[2] + dp[day + 30]);
            }
        }
        return dp[1];
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-cost-for-tickets/
/// Author : liuyubobobo
/// Time   : 2019-01-28

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


/// Memory Search
/// No need have 365 states, n states would be enough :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(len(days))
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {

        int n = days.size();
        vector<int> dp(n, -1);

        return dfs(days, 0, n, costs, dp);
    }

private:
    int dfs(const vector<int>& days, int index, int n, const vector<int>& costs, vector<int>& dp){

        if(index >= n) return 0;
        if(dp[index] != -1) return dp[index];

        int res = costs[0] + dfs(days, index + 1, n, costs, dp);

        int i1 = 0;
        for(; i1 < n; i1 ++)
            if(days[i1] >= days[index] + 7) break;
        res = min(res, costs[1] + dfs(days, i1, n, costs, dp));

        int i2 = 0;
        for(; i2 < n; i2 ++)
            if(days[i2] >= days[index] + 30) break;
        res = min(res, costs[2] + dfs(days, i2, n, costs, dp));

        return dp[index] = res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-cost-for-tickets/
/// Author : liuyubobobo
/// Time   : 2019-01-28

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


/// Memory Search
/// No need have 365 states, n states would be enough :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(len(days))
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {

        int n = days.size();
        vector<int> dp(n + 1, 0);
        dp[n - 1] = costs[0];
        for(int i = n - 2; i >= 0; i --){
            dp[i] = costs[0] + dp[i + 1];

            int i1 = 0;
            for(; i1 < n; i1 ++)
                if(days[i1] >= days[i] + 7) break;
            dp[i] = min(dp[i], costs[1] + dp[i1]);

            int i2 = 0;
            for(; i2 < n; i2 ++)
                if(days[i2] >= days[i] + 30) break;
            dp[i] = min(dp[i], costs[2] + dp[i2]);
        }

        return dp[0];
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-cost-for-tickets/
/// Author : liuyubobobo
/// Time   : 2019-01-26

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


/// Memory Search
/// No need have 365 states, n states would be enough :-)
/// Since days is in increasing order, we can use binary search to get next state more quickly :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(len(days))
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {

        int n = days.size();
        vector<int> dp(n, -1);

        return dfs(days, 0, n, costs, dp);
    }

private:
    int dfs(const vector<int>& days, int index, int n, const vector<int>& costs, vector<int>& dp){

        if(index >= n) return 0;
        if(dp[index] != -1) return dp[index];

        int res = costs[0] + dfs(days, index + 1, n, costs, dp);

        int i1 = upper_bound(days.begin(), days.end(), days[index] + 6) - days.begin();
        res = min(res, costs[1] + dfs(days, i1, n, costs, dp));

        int i2 = upper_bound(days.begin(), days.end(), days[index] + 29) - days.begin();
        res = min(res, costs[2] + dfs(days, i2, n, costs, dp));

        return dp[index] = res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-cost-for-tickets/
/// Author : liuyubobobo
/// Time   : 2019-01-28

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


/// Dynamic Programming
/// No need have 365 states, n states would be enough :-)
/// Since days is in increasing order, we can use binary search to get next state more quickly :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(len(days))
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {

        int n = days.size();
        vector<int> dp(n + 1, 0);
        dp[n - 1] = costs[0];
        for(int i = n - 2; i >= 0; i --){
            dp[i] = costs[0] + dp[i + 1];

            int i1 = upper_bound(days.begin(), days.end(), days[i] + 6) - days.begin();
            dp[i] = min(dp[i], costs[1] + dp[i1]);

            int i2 = upper_bound(days.begin(), days.end(), days[i] + 29) - days.begin();
            dp[i] = min(dp[i], costs[2] + dp[i2]);
        }

        return dp[0];
    }
};


int main() {

    return 0;
}