題目： LeetCode - 983. Minimum Cost For Tickets

題目說明

給兩個陣列，days 代表需要坐火車的日期，costs 代表火車的日票、周票、月票價格。求所有需要搭火車的日期都能搭火車的最小花費。

解題思路

動態規劃，若當天需要搭火車，最佳解為 當天買一張日票、六天前買一張周票、29天前買一張月票，三者的價格的最小值。若當天不需要搭火車，價格就為前一天的價格。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp(days.back() + 1);
        unordered_set<int> set(days.begin(), days.end());
        for(int i = 1; i <= days.back(); ++i)
        {
            if(!set.count(i)) { dp[i] = dp[i - 1]; continue; }
            dp[i] = min(dp[max(0, i - 1)] + costs[0], min(dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2]));
        }
        return dp[days.back()];
    }
};