C++でのチケットの最小コスト

電車旅行で人気のある国があるとすると、1年前に電車旅行を計画しています。私たちは、私たちが旅行する年の日を保持している配列を持っています。毎日は1から365までの整数です。列車の切符は3つの異なる方法で販売されます-

• 1日パスは費用[0]ドルで販売されています;

• 1日パスは費用[0]ドルで販売されています;

• 30日パスは費用[2]ドルで販売されています。

ここでは、パスにより、何日も連続して旅行することができます。たとえば、2日目に7日間のパスを1つ取得した場合、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日間パスを購入したので、コスト[0] =$ 2、つまり20日目をカバーします。合計で$11が費やされます。

これを解決するには、次の手順に従います-

• サイズ366のdpという1つの配列を作成します

• j：=0

• 1から366の範囲のiの場合

  • dp [i]：=コスト[0] + dp [i-1]

  • i – 7> =0の場合、dp [i]：=最小のdp[i-7]+コスト[1]およびdp[i]

  • i – 30> =0の場合、dp [i]：=最小のdp[i-30]+コスト[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