Pythonで一日中旅行するための最低バス料金を見つけるプログラム？

日と呼ばれるソートされた番号のリストがあるとします。ここで、毎日バスに乗る必要があります。私たちは、一日中旅行するのにかかる最低の費用を見つけなければなりません。バスの切符は3種類あります。 2ドルの1日パス7ドルの7日パス25ドルの30日パス

したがって、入力が日数=[1、3、5、6、28]の場合、出力は9になります。これは、最初に7日間のパスを購入し、次に1-を購入することで最低のコストを達成できるためです。 29日目の1日パス。

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

• n：=最大日数

• 日：=日からの新しいセット

• dp：=[0] *（n + 1）

• 1からn+1の範囲のiの場合、実行

  • 日数のiがゼロ以外の場合、

    • i> =30の場合、

      • dp [i]：=最小dp [i-1] + 2、dp [i-7] + 7、dp [i-30] + 25

    • それ以外の場合、i> =7の場合、

      • dp [i]：=最小dp [i-1] + 2、dp [i-7] + 7、25

    • それ以外の場合

      • dp [i]：=最小のdp [i-1] + 2、7

  • それ以外の場合

    • dp [i]：=dp [i-1]

• dp [n]

  を返します

理解を深めるために、次の実装を見てみましょう。

例

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