C++ 中最低票价计算
假设某个国家/地区很适合乘坐火车旅行，我们提前一年计划了一些火车旅行。我们有一个数组，用于保存我们将在一年中旅行的天数。每一天都是一个从 1 到 365 的整数。火车票以三种不同的方式出售 −
1 日通票售价为 costs[0] 美元;
1 日通票售价为 costs[0] 美元;
30 日通票售价为 costs[2] 美元。
这里的通票允许连续旅行天数为 0 天。例如，如果我们在第 2 天拿到一张 7 日通票，那么我们可以连续旅行 7 天(第 2、3、4、5、6、7 和 8 天)。我们需要找出在给定的日期列表中每天旅行所需的最低美元金额。因此，如果输入为 [1,4,6,7,8,20]，费用为 [2,7,15]，则输出为 11。
第 1 天，我们购买了 1 天通票，费用为 costs[0] = $2，涵盖第 1 天;第 3 天，我们购买了 7 天通票，费用为 cost[1] = $7，涵盖第 3 至第 9 天;第 20 天，我们再次购买了 1 天通票，费用为 cost[0] = $2，涵盖第 20 天。因此，总共花费了 $11。
为了解决这个问题，我们将遵循以下步骤 −
创建一个名为 dp 的数组，大小为 366
j := 0
i 的范围为 1 到 366
dp[i] := cost[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]
return 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
