假设有一个在火车旅行中很受欢迎的国家，我们已经计划提前一年进行一些火车旅行。我们有一个数组，保存着我们每年旅行的日子。每天是1到365之间的整数。火车票以三种不同的方式出售-
1天通行证的售价为[0]美元；
1天通行证的售价为[0]美元；
30天的通行证售价为成本[2]美元。
在这里，通行证允许连续几天旅行。例如，如果我们在第2天获得一张7天通行证，那么我们可以连续旅行7天：连续一天（2、3、4、5、6、7和8）。我们必须在给定的天数列表中找到每天需要旅行的最少钱数。因此，如果输入为[1,4,6,7,8,20]，成本为[2,7,15]，那么输出将为11。
在第1天，我们购买了1天的通行证，费用为[0] = $2，即第1天，在第3天，我们购买了7天的通行证，所以成本[1] = $7，即第3至9天，在第20天，又购买了1天的通行证，因此cost [0] = $2，即第20天的费用。因此，总共花费了$11。
为了解决这个问题，我们将遵循以下步骤-
创建一个名为dp的数组，大小为366
j：= 0
适用于1至366的范围
dp [i]：=成本[0] + dp [i-1]
如果i – 7> = 0，则dp [i]：= dp [i-7]的最小值+ cost [1]和dp [i]
如果i – 30> = 0，则dp [i]：= dp [i-30]的最小值+ cost [2]和dp [i]
如果j <days数组的大小并且days [j] = i，则将j增加1，否则dp [i]：= dp [i]的最小值，dp [i – 1]
返回dp [365]
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
vector <int> dp(366);
int j = 0;
for(int i = 1; i < 366; i++){
dp[i] = costs[0] + dp[i - 1];
if(i - 7 >= 0){
dp[i] = min(dp[i - 7] + costs[1], dp[i]);
}
if(i - 30 >= 0){
dp[i] = min(dp[i - 30] + costs[2], dp[i]);
}
if(j < days.size() && days[j] == i){
j++;
}else
dp[i] = min(dp[i], dp[i - 1]);
}
return dp[365];
}
};
main(){
vector<int> v = {1,4,6,7,8,20};
vector<int> v1 = {2,7,15};
Solution ob;
cout << (ob.mincostTickets(v, v1));
}[1,4,6,7,8,20] [2,7,15]
输出结果
11