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