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 次瀏覽

開啟您的 職業生涯

完成課程獲得認證

開始學習