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

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

उदाहरण के लिए, यदि इनपुट 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।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम रिकर्सन + मेमोइजेशन का उपयोग करेंगे:

switch := की 0 के लिए nums0, और की 1 के लिए nums1 वाला मैप
search(idx, nums) फंक्शन परिभाषित करें:
- यदि idx >= switch[nums] का आकार है, तो inf लौटाएं
- यदि idx == switch[nums] का आकार - 1 है, तो switch[nums][-1] लौटाएं
- c := inf
- i को 1 से dist तक लूप चलाएं:
  - c := min(c, switch[nums][idx] + search(idx + i, nums))
  - c := min(c, switch[nums][idx] + cost + search(idx + i, not nums))
- c लौटाएं
मुख्य मेथड से min(search(0, 0), search(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