程序在Python中查找大小为k的递增子序列数

假设我们有一个叫做nums的数字列表，还有另一个值k，我们必须找到大小为k且严格增加的子序列数。如果答案很大，则将其修改为10 ^ 9 + 7。

因此，如果输入像nums = [2，3，4，1] k = 2，那么输出将是3，因为我们有大小为2的子序列：[2，3]，[3，4]， [2，4]。

范例(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