C ++中的最低票价
假设有一个在火车旅行中很受欢迎的国家，我们已经计划提前一年进行一些火车旅行。我们有一个数组，保存着我们每年旅行的日子。每天是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