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));
}