โปรแกรมหาจำนวนลำดับการเพิ่มขึ้นของขนาด k ใน Python

สมมุติว่าเรามีรายการของตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาจำนวนลำดับของขนาด k ที่เพิ่มจำนวนขึ้นเรื่อยๆ หากคำตอบมีขนาดใหญ่มาก ให้แก้ไข 10^9 + 7

ดังนั้น หากอินพุตเท่ากับ nums =[2, 3, 4, 1] k =2 เอาต์พุตจะเป็น 3 เนื่องจากเรามีลำดับย่อยของขนาด 2:[2, 3], [3, 4] [2, 4].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=10^9 + 7
• dp :=รายการขนาดเท่ากับ nums และเติมด้วย 1
• ทำซ้ำ k ครั้งต่อไปนี้ ทำ
  • สำหรับ j ในช่วงขนาด dp - 1 ถึง 0, ลดลง 1 ทำ
    • dp[j] :=0
    • สำหรับฉันในช่วง 0 ถึง j ทำ
      • ถ้า nums[i]
      • dp[j] :=dp[j] + dp[i]

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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