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

假设我们有一个名为nums的数字列表，还有另一个值k，我们必须找到大小为k且严格递增的子序列的数量。如果答案非常大，则对10 ^ 9 + 7取模。

因此，如果输入类似于nums = [2, 3, 4, 1] k = 2，则输出将为3，因为我们有大小为2的子序列：[2, 3]，[3, 4]，[2, 4]。

要解决此问题，我们将按照以下步骤进行 –

m：=10 ^ 9 + 7
dp：大小与nums相同的列表，并将其填充为1
迭代以下k次，执行
- 对于j在dp大小的范围内，从dp-1到0递减，执行
  - dp [j]：= 0
  - 对于i在0到j的范围内，执行
  - 如果nums [i]＜nums [j]，则
    - dp [j]：= dp [j] + dp [i]
返回（dp中所有元素的总和）mod m

更多Python相关文章，请阅读：Python 教程

示例（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))