पायथन में आकार k के बढ़ते सबसीक्वेंस की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक लिस्ट है और एक मान k है, हमें आकार k के उन सबसीक्वेंस की संख्या ढूंढनी है जो सख्ती से बढ़ते हैं। यदि उत्तर बहुत बड़ा है, तो इसे 10^9 + 7 से मॉड करें।

उदाहरण के लिए, यदि इनपुट nums = [2, 3, 4, 1], k = 2 है, तो आउटपुट 3 होगा, क्योंकि हमारे पास आकार 2 के सबसीक्वेंस हैं: [2, 3], [3, 4], [2, 4]।

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

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

• m := 10^9 + 7
• dp := nums के आकार की लिस्ट, 1 से भरी हुई
• k - 1 बार निम्नलिखित दोहराएं:
  • j को dp के आकार - 1 से 0 तक घटाते हुए लूप चलाएं:
    • dp[j] := 0
    • i को 0 से j-1 तक लूप चलाएं:
      • यदि nums[i] < nums[j] है, तो dp[j] := dp[j] + dp[i]
• (dp के सभी तत्वों का योग) mod m लौटाएं

पायथन कार्यान्वयन

class Solution:
    def solve(self, nums, k):
        m = 10 ** 9 + 7
        dp = [1] * len(nums)
        for _ in range(k - 1):
            for j in range(len(dp) - 1, -1, -1):
                dp[j] = 0
                for i in range(j):
                    if nums[i] < nums[j]:
                        dp[j] += dp[i]
        return sum(dp) % m

ob = Solution()
nums = [2, 3, 4, 1]
k = 2
print(ob.solve(nums, k))

इनपुट

[2, 3, 4, 1], 2

आउटपुट

3