Pythonでサイズkの増加するサブシーケンスの数を見つけるプログラム

numsと呼ばれる数のリストと別の値kがあるとすると、厳密に増加しているサイズkのサブシーケンスの数を見つける必要があります。答えが非常に大きい場合は、10 ^ 9+7で変更します。

したがって、入力がnums =[2、3、4、1] k =2のような場合、サイズ2のサブシーケンスがあるため、出力は3になります。[2、3]、[3、4]、 [2、4]。

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7
• dp：=numsと同じサイズのリストで、1を入力します
• 次のk回繰り返します。
  • dp-1から0の範囲サイズのjの場合、1ずつ減らします。
    • dp [j]：=0
    • 0からjの範囲のiについては、
      • nums [i]
      • dp [j]：=dp [j] + dp [i]

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