Pythonで指定された2つのリストのいずれかの最終インデックスに到達するためのコストを見つけるためのプログラム

同じ長さの数値nums0とnums1の2つのリストがあり、距離としてd、コストとしてcの他の2つの値があるとします。 nums0またはnums1のいずれかでインデックス0から開始し、いずれかのリストの最終インデックスで終了したい場合。これで、各ラウンドで、コストのコストについて他のリストに切り替えることを選択できます。次に、最大d距離離れたところにジャンプできます。ここで、インデックスに着陸するためのcコストは、その時点での値です。したがって、タスクを完了するために可能な最小の総コストを見つける必要があります。

したがって、入力がnums0 =[2、3、10、10、6] nums1 =[10、10、4、5、100] d =2 c =3の場合、出力は18になります。 2から始めて、2番目のリストを4に切り替え、再び最初のリストを6に戻します。したがって、コスト2 + 4 + 6 =12で、コスト3で2回切り替えると、合計は18になります。

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

• switch：=nums0にはキー0、nums1にはキー1のマップ
• 関数search（）を定義します。これにはidx、numsが必要です
• idx> =switch [nums]のサイズの場合、
  • return inf
• idxがswitch[nums]-1のサイズと同じ場合、
  • リターンスイッチ[nums、-1]
• c：=inf
• 範囲1からdist+1のiの場合、実行
  • c：=cとswitch[nums、idx] + search（idx + i、nums）の最小値
  • c：=最小のcとswitch [nums、idx] + cost + search（idx + i、invert of nums）
• return c
• メインメソッドから次の手順を実行します-
• search（0、0）とsearch（0、1）の最小値を返します

例（Python）

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

class Solution:
   def solve(self, nums0, nums1, dist, cost):
      switch = {0: nums0, 1: nums1}
      def search(idx, nums):
         if idx >= len(switch[nums]):
            return float("inf")
         if idx == len(switch[nums]) - 1:
            return switch[nums][-1]
         c = float("inf")
         for i in range(1, dist + 1):
            c = min(c, switch[nums][idx] + search(idx + i, nums))
            c = min(c, switch[nums][idx] + cost + search(idx + i, int(not nums)))
         return c
      return min(search(0, 0), search(0, 1))
ob = Solution()
nums0 = [2, 3, 10, 10, 6]
nums1 = [10, 10, 4, 5, 100]
d = 2
c = 3
print(ob.solve(nums0, nums1, d, c))

入力

[2, 3, 10, 10, 6],[10, 10, 4, 5, 100], 2, 3

出力

18