Chương trình tìm số lượng dãy con có kích thước k tăng dần trong Python

Giả sử chúng ta có một danh sách các số gọi là num và một giá trị khác k, chúng ta phải tìm số lượng các dãy con có kích thước k đang tăng dần. Nếu câu trả lời là rất lớn, hãy sửa đổi nó theo 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là nums =[2, 3, 4, 1] k =2, thì đầu ra sẽ là 3, vì chúng ta có các dãy con có kích thước 2:[2, 3], [3, 4], [2, 4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7
• dp:=một danh sách có kích thước giống như nums và điền bằng 1
• lặp lại k lần sau, thực hiện
  • cho j trong phạm vi kích thước dp - 1 đến 0, giảm 1, thực hiện
    • dp [j]:=0
    • đối với tôi trong phạm vi từ 0 đến j, thực hiện
      • nếu nums [i]
      • dp [j]:=dp [j] + dp [i]

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[2, 3, 4, 1], 2

Đầu ra

3