C++で解く鉄道チケットの最小費用問題 ― 動的計画法によるアプローチ

鉄道旅行が盛んな国を、1年先の計画で旅することになったとします。旅行予定日は配列として与えられ、各日は1から365までの整数で表されます。切符（パス）は次の3種類が販売されています。

• 1日パス：costs[0] ドル
• 7日パス：costs[1] ドル
• 30日パス：costs[2] ドル

それぞれのパスは、購入した日からその期間分だけ連続して乗車できます。たとえば2日に7日パスを購入すれば、2日・3日・4日・5日・6日・7日・8日の7日間にわたって旅行可能です。求めるのは、与えられた旅行日リストのすべての日をカバーするために必要な最小金額です。

入力例と考え方

たとえば days = [1,4,6,7,8,20]、costs = [2,7,15] が入力された場合、出力は 11 になります。具体的には、次のようにパスを購入すればすべての旅行日をカバーできます。

• 1日に1日パス（costs[0] = 2ドル）を購入し、1日をカバー
• 3日に7日パス（costs[1] = 7ドル）を購入し、3日〜9日をカバー（4日・6日・7日・8日の旅行日に対応）
• 20日に1日パス（costs[0] = 2ドル）を購入し、20日をカバー

合計は 2 + 7 + 2 = 11ドルとなり、これがこのケースでの最小費用です。

動的計画法（DP）による解き方

この問題は動的計画法で効率よく解けます。dp[i] を「i日目までのすべての旅行日をカバーするのに必要な最小費用」と定義します。手順は以下のとおりです。

• サイズ366の配列 dp を用意する
• j := 0 とする（days 配列を読み進めるためのインデックス）
• i を 1 から 365 まで繰り返す
  • dp[i] := costs[0] + dp[i - 1]（1日パスを購入した場合のコスト）
  • i − 7 ≥ 0 ならば、dp[i] := min(dp[i - 7] + costs[1], dp[i])（7日パスを購入した場合と比較）
  • i − 30 ≥ 0 ならば、dp[i] := min(dp[i - 30] + costs[2], dp[i])（30日パスを購入した場合と比較）
  • j が days の範囲内かつ days[j] == i なら j を1増やす（i日目が旅行日の場合）。そうでなければ dp[i] := min(dp[i], dp[i - 1])（旅行日でない日は前日と同じ費用で済む）
• 最後に dp[365] を返す

ポイントは、旅行日でない日は追加の支出が不要なため dp[i - 1] をそのまま引き継げる点です。これにより、3種類のパスをどのタイミングで買うのが最も得かを自動的に判断できます。

C++実装例

#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

計算量

探索対象は1年間（最大365日）のみなので、時間計算量・空間計算量はいずれも O(365)、つまり定数時間・定数メモリで処理できます。旅行日数を N、期間の上限を D 日と一般化した場合は O(D) の時間・空間計算量となります。