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

สมมติว่าเรามีรายการตัวเลข nums และค่า k เราต้องการหาจำนวนลำดับย่อย (subsequences) ขนาด k ที่เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) ถ้าคำตอบมากเกินไป modulo 10^9+7

เช่น nums = [2, 3, 4, 1] k = 2 ผลลัพธ์ = 3 ลำดับย่อยขนาด 2: [2,3], [3,4], [2,4]

ขั้นตอนการแก้ปัญหา (DP Bottom-up)

m := 10^9 + 7
dp := array ขนาด len(nums) เติม 1 (dp[i] = จำนวน subsequence ขนาดปัจจุบันลงท้ายที่ i)
ทำซ้ำ k-1 รอบ:
- วน j จาก len(dp)-1 ลง 0:
  - dp[j] = 0
  - วน i = 0..j-1: ถ้า nums[i] < nums[j] ให้ dp[j] += dp[i]
คืน sum(dp) % 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