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大小-1到0，递减1，执行：
    • dp[j] := 0
    • 对于i从0到j，执行：
      • 如果nums[i] < nums[j]，则：
        • dp[j] := dp[j] + dp[i]
• 返回(dp中所有元素的总和)模m

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

Arnab Chakraborty

更新于: 2020年12月12日

408 次浏览

开启您的 职业生涯

完成课程获得认证

开始学习