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

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और एक अन्य मान k भी है, हमें आकार k के बाद के क्रमों की संख्या ज्ञात करनी है जो सख्ती से बढ़ रहे हैं। अगर उत्तर बहुत बड़ा है, तो इसे 10^9 + 7 से संशोधित करें।

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

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

• म :=10^9 + 7
• dp :=अंकों के समान आकार की सूची और 1 से भरें
• निम्न k बार पुनरावृति करें, करें
  • j के लिए dp - 1 से 0 के श्रेणी आकार में, 1 से घटाएं
    • dp[j] :=0
    • मैं के लिए 0 से j की सीमा में, करते हैं
      • यदि अंक[i] <अंक[j], तो
        • dp[j] :=dp[j] + dp[i]
• रिटर्न (डीपी में सभी तत्वों का योग) मॉड एम

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

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

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