数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的最低票价
假设有一个以火车旅行闻名的国家，我们已经提前一年计划了一些火车旅行。我们有一个数组，其中包含我们将旅行的年份中的日期。每一天都是从 1 到 365 的整数。火车票以三种不同的方式出售：
1 日票售价为 costs[0] 美元；
1 日票售价为 costs[0] 美元；
7 日票售价为 costs[1] 美元；
30 日票售价为 costs[2] 美元。
这些通行证允许连续旅行这么多天。例如，如果我们在第 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[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
更新于：2020 年 5 月 2 日
