पायथन में दी गई दो सूचियों में से किसी के अंतिम सूचकांक तक पहुंचने के लिए लागत खोजने का कार्यक्रम

मान लीजिए कि हमारे पास समान लंबाई की संख्या nums0 और nums1 की दो सूचियां हैं और दो अन्य मान d दूरी और c लागत के रूप में हैं। यदि हम इंडेक्स 0 से nums0 या nums1 पर शुरू करते हैं और किसी भी सूची के अंतिम इंडेक्स पर समाप्त होना चाहते हैं। अब, प्रत्येक दौर में, हम लागत की लागत के लिए दूसरी सूची में स्विच करना चुन सकते हैं। तब हम अधिकतम d दूरी पर आगे बढ़ सकते हैं, जहां एक सूचकांक पर उतरने की c लागत उस बिंदु पर मूल्य है। इसलिए हमें कार्य को पूरा करने के लिए संभव न्यूनतम कुल लागत का पता लगाना होगा।

इसलिए, यदि इनपुट nums0 =[2, 3, 10, 10, 6] nums1 =[10, 10, 4, 5, 100] d =2 c =3 जैसा है, तो आउटपुट 18 होगा, जैसा कि हम कर सकते हैं 2 से शुरू करें, फिर दूसरी सूची में 4 पर स्विच करें, फिर से पहली सूची में 6 पर स्विच करें। तो लागत 2 + 4 + 6 =12 और लागत 3 के साथ दो बार स्विच करें, इसलिए कुल 18 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

स्विच :=nums0 के लिए कुंजी 0 वाला नक्शा, और nums1 के लिए कुंजी 1
फ़ंक्शन को परिभाषित करें search() । इसमें idx, अंक लगेंगे
यदि idx>=स्विच का आकार [संख्या] , तो
- वापसी की जानकारी
यदि आईडीएक्स स्विच के आकार के समान है [संख्या] -1, तो
- वापसी स्विच[nums, -1]
c :=inf
i श्रेणी 1 से लेकर जिला + 1 तक के लिए
- c :=न्यूनतम c और स्विच[nums, idx] + search(idx + i, nums)
- c :=न्यूनतम c और स्विच [nums, idx] + लागत + खोज (idx + i, अंकों का उलटा)
वापसी सी
मुख्य विधि से निम्न कार्य करें -
खोज का न्यूनतम लौटाएं(0, 0) और खोज(0, 1)

उदाहरण (पायथन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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