पायथन में लगातार 3 तत्वों से कम से कम एक लेकर न्यूनतम सम सबसीक्वेंस खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें दी गई सूची से एक न्यूनतम सम सबसीक्वेंस ढूंढना है जैसे कि लगातार तीन संख्याओं के सभी समूहों के लिए कम से कम एक संख्या चुनी गई हो। यदि दी गई सूची की लंबाई 3 से कम है, तो फिर भी एक संख्या चुनी जानी चाहिए।

उदाहरण के लिए, यदि इनपुट nums = [2, 3, 4, 5, 6, 7] है, तो आउटपुट 7 होगा, क्योंकि हम 2 और 5 चुन सकते हैं।

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

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• n := len(nums)
• यदि n == 0, तो 0 लौटाएं
• यदि n == 1, तो nums[0] लौटाएं
• यदि n == 2, तो min(nums[0], nums[1]) लौटाएं
• table := आकार n की सूची, 0 से भरी
• table[0] := nums[0], table[1] := nums[1], table[2] := nums[2]
• i को 3 से n तक:
  • table[i] := nums[i] + min(table[i-3], table[i-2], table[i-1])
• res := min(table[n-1], table[n-2], table[n-3])
• res लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return min(nums[0], nums[1])
        table = [0] * n
        table[0] = nums[0]
        table[1] = nums[1]
        table[2] = nums[2]
        for i in range(3, n):
            table[i] = nums[i] + min(table[i-3], table[i-2], table[i-1])
        res = min(table[n-1], table[n-2], table[n-3])
        return res

ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

इनपुट

[2, 3, 4, 5, 6, 7]

आउटपुट

7