983. Minimum Cost For Tickets

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. 1 <= days.length <= 365

2. 1 <= days[i] <= 365

3. days is in strictly increasing order.

4. costs.length == 3

5. 1 <= costs[i] <= 1000

利用bottom-up DP維護一個1D array去紀錄最小車票成本。c[i]代表到第i天的最少車票花費。

dp state transition: c[i] = c[i - 1] 如果第i天沒有要搭車出遊 c[i] = min({c[i - 1] + costs[0], c[i - 7] + costs[1], c[i - 30] + costs[2] }) 如果第i天有要搭車出遊

int mincostTickets(vector<int>& days, vector<int>& costs) { // time: O(n); space: O(1)
    vector<int> c(366, -1); // c[i]: the minimum cost until ith day
    for (int d : days) c[d] = 0; // initialization
    c[0] = 0;
    for (int i = 1; i <= 365; ++i) {
        if (c[i] == -1) {
            c[i] = c[i - 1];
            continue;
        }
        c[i] = min({c[max(0, i - 1)] + costs[0], c[max(0, i - 7)] + costs[1], c[max(0, i - 30)] + costs[2]});
    }
    return c.back();
}

int mincostTickets(vector<int>& days, vector<int>& costs) { // time: O(n); space: O(n)
    unordered_set<int> st(days.begin(), days.end());
    vector<int> c(366, 0); // c[i]: the minimum cost until ith day
    for (int i = 1; i <= 365; ++i) {
        if (!st.count(i)) {
            c[i] = c[i - 1];
        } else {
            c[i] = min({c[max(0, i - 1)] + costs[0], c[max(0, i - 7)] + costs[1], c[max(0, i - 30)] + costs[2]});
        }
    }
    return c.back();
}

可以只使用一個size為31的array而不需要用到size為366的array去紀錄，利用取餘(modulus)的概念。

int mincostTickets(vector<int>& days, vector<int>& costs) { // time: O(n); space: O(n)
    unordered_set<int> st(days.begin(), days.end());
    vector<int> c(31, 0);
    for (int i = days.front(); i <= days.back(); ++i) {
        if (!st.count(i)) {
            c[i % 31] = c[(i - 1) % 31];
        } else {
            c[i % 31] = min({c[max(0, i - 1) % 31] + costs[0], c[max(0, i - 7) % 31] + costs[1], c[max(0, i - 30) % 31] + costs[2]});
        }
    }
    return c[days.back() % 31];
}

前面的方法都是track calendar days，最後一個方法用2個queue去紀錄有效期間內的7日票和30日票，然後直接根據travel days來計算而不是掃描所有的calendar days。

// Track Travel Days
int mincostTickets(vector<int>& days, vector<int>& costs) { // time: O(n); space: O(1)
    queue<pair<int, int> > last7, last30;
    int cost = 0;
    for (int day : days) {
        while (!last7.empty() && last7.front().first + 7 <= day) last7.pop();
        while (!last30.empty() && last30.front().first + 30 <= day) last30.pop();
        last7.push({day, cost + costs[1]});
        last30.push({day, cost + costs[2]});
        cost = min({cost + costs[0], last7.front().second, last30.front().second});
    }
    return cost;
}

這題基本上想法和322. Coin Change相似。