题目描述
题目链接: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 from1
to365
.Train tickets are sold in 3 different ways:
a 1-day pass is sold for
costs[0]
dollars; a 7-day pass is sold forcosts[1]
dollars; a 30-day pass is sold forcosts[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
.
例子
例子 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.
例子 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
解题思路
通常来说遇到这种求最小花费的题首先都可以考虑能不能用动态规划来做。这道题是可以的,状态量就是第 i
天的最小花费,而转移方程为比较以下三种情况,取最小值:
- 一天前的最小花费 + 一天票钱
- 七天前的最小花费 + 七天票钱
- 30天前最小花费 + 30天票钱
同时要注意一下边界条件:在前7天和前30天的时候,取第0天花费(即0花费)作为起始花费。代码如下所示:
#include <vector>
#include <bits/stdc++.h>
class Solution {
public:
int mincostTickets(std::vector<int>& days, std::vector<int>& costs) {
std::vector<int> min_costs(366, INT_MAX);
min_costs[0] = 0;
for(int day: days) {
min_costs[day] = 0; // mark for travel days
}
for (int i = 1; i < 366; i++) {
if (min_costs[i] == INT_MAX) {
min_costs[i] = min_costs[i - 1];
} else {
int min_cost = min_costs[i - 1] + costs[0];
min_cost = std::min(min_costs[std::max(0, i - 7)] + costs[1], min_cost);
min_cost = std::min(min_costs[std::max(0, i - 30)] + costs[2], min_cost);
min_costs[i] = min_cost;
}
}
return min_costs.back();
}
};
- 时间复杂度:O(1)—-常数时间(366)
- 空间复杂度:O(1)—-常数空间(366)