diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_cost_ticket.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'min_cost_ticket.cpp')
-rw-r--r-- | min_cost_ticket.cpp | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/min_cost_ticket.cpp b/min_cost_ticket.cpp new file mode 100644 index 0000000..1d00853 --- /dev/null +++ b/min_cost_ticket.cpp @@ -0,0 +1,42 @@ +// 983. Minimum Cost For Tickets +#include "leetcode.h" + +/* + * you have planned some train traveling one year in advance. the days of the + * year in which you will travel are given as an integer array 'days'. each day + * is an integer 1 - 365. train tickets are sold in three different ways: 1 day + * pass sold for 'costs[0]' dollars 7 day pass sold for 'costs[1]' dollars 30 + * day pass sold for 'costs[2]' dollars the passes allow that many days of + * consecutive travel. return mininum number of dollars you need to travel every + * day in the given list of days. + */ + +class Solution { +public: + int mincostTickets(vector<int> &days, vector<int> &costs) { + unordered_map<int, int> tickets; + tickets[1] = costs[0]; + tickets[7] = costs[1]; + tickets[30] = costs[2]; + vector<int> dp(366, INT_MAX); + dp[0] = 0; + for (int i = 1; i < 366; i++) { + if (find(days.begin(), days.end(), i) == days.end()) { + dp[i] = dp[i - 1]; + continue; + } + for (auto t : tickets) + dp[i] = min(dp[i], dp[max(0, i - t.first)] + t.second); + } + return dp[365]; + } +}; + +int main() { + Solution obj; + vector<int> d1 = {1, 4, 6, 7, 8, 20}, + d2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31}; + vector<int> c1 = {2, 7, 15}; + printf("%d\n", obj.mincostTickets(d1, c1)); // expect: 11 + printf("%d\n", obj.mincostTickets(d2, c1)); // expect: 17 +} |