Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Python

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

Cho danh sách số nums và số nguyên k. Đếm số dãy con (subsequence) kích thước k tăng chặt (strictly increasing). Kết quả modulo 10⁹+7.

Ví dụ: nums = [2,3,4,1], k=2 → các dãy con: [2,3], [3,4], [2,4] → kết quả 3.

Giải thuật (DP lặp k lần)

  • dp[i] = số dãy con tăng kết thúc tại i với độ dài hiện tại.
  • Khởi tạo dp = [1]*n (độ dài 1).
  • Lặp k-1 lần mở rộng độ dài:
    • Duyệt j từ n-1 xuống 0: reset dp[j]=0, cộng dồn dp[i] cho mọi i với nums[i] < nums[j].
  • Kết quả = sum(dp) % MOD.

Mã nguồn Python

class Solution:
    def solve(self, nums, k):
        MOD = 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[j] + dp[i]) % MOD
        return sum(dp) % MOD

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

Đầu vào

[2, 3, 4, 1], 2

Đầu ra

3