Pythonで全移動日をカバーするバス乗車券の最低料金を求めるプログラム（動的計画法）

問題の概要

ソート済みの整数リスト days が与えられます。このリストに含まれる各日は、必ずバスで移動しなければならない日を表しています。すべての移動日をカバーするために必要な最低料金を求めましょう。

利用できるバス乗車券は次の3種類です。

• 1日乗車券：2ドル
• 7日乗車券：7ドル
• 30日乗車券：25ドル

入出力の例

たとえば、入力が days = [1, 3, 5, 6, 28] の場合、出力は 9 になります。これは、1日目に7日乗車券（7ドル）を購入して1〜7日目の移動をまとめてカバーし、残りの28日目に1日乗車券（2ドル）を購入すればよいためです。合計は 7 + 2 = 9 ドルとなり、これが最安の組み合わせになります。

解き方：動的計画法（DP）

この問題は動的計画法を使うと効率的に解けます。dp[i] を「i 日目までの移動をすべてカバーするのに必要な最低料金」と定義します。各日について、どの乗車券を購入するかを選択し、その中で最も安い金額を採用していきます。

アルゴリズムの手順

1. n を days の最大値とする。
2. days を集合（set）に変換し、高速な存在判定を可能にする。
3. 長さ n+1 のDP配列 dp を初期値 0 で作成する。
4. i を 1 から n まで順に処理する。
   • i が days に含まれる（移動が必要な）日の場合：
     • i ≥ 30 のとき：dp[i] = min(dp[i-1] + 2, dp[i-7] + 7, dp[i-30] + 25)
     • i ≥ 7 のとき：dp[i] = min(dp[i-1] + 2, dp[i-7] + 7, 25)（i-30 が負になるため、30日券は定額の 25 と比較する）
     • それ以外のとき：dp[i] = min(dp[i-1] + 2, 7)
   • i が days に含まれない日の場合：移動がないため dp[i] = dp[i-1]（料金は変わらない）。
5. 最後に dp[n] を返す。

Pythonでの実装例

class Solution:
    def solve(self, days):

        n = max(days)
        days = set(days)

        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            if i in days:
                if i >= 30:
                    dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, dp[i - 30] + 25)
                elif i >= 7:
                    dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, 25)
                else:
                    dp[i] = min(dp[i - 1] + 2, 7)
            else:
                dp[i] = dp[i - 1]

        return dp[n]

ob = Solution()
days = [1, 3, 5, 6, 28]
print(ob.solve(days))

実行結果

入力：

[1, 3, 5, 6, 28]

出力：

9

計算量について

このアルゴリズムは、1日目から最終日までを一度ずつ走査するだけなので、時間計算量は O(n)、DP配列を保持するため空間計算量も O(n) です（n は移動期間の日数）。移動日が飛び飛びでも正しく対応でき、乗車券の組み合わせを全探索するよりもはるかに効率的です。