Pythonで長さkの増加部分列の個数を動的計画法で求める方法

数値のリスト nums と整数 k が与えられたとき、「厳密に増加する」サイズ k の部分列(サブシーケンス)が何個存在するかを求めます。答えが非常に大きくなる可能性があるため、10^9 + 7 で割った余りを返します。

たとえば、nums = [2, 3, 4, 1]、k = 2 の場合、出力は 3 になります。これは、サイズ 2 の増加部分列として [2, 3]、[3, 4]、[2, 4] の 3 つが存在するためです。

解法のアプローチ

この問題は動的計画法(DP)を用いて効率的に解くことができます。dp[j] は「インデックス j の要素を末尾とする、現在の長さの増加部分列の個数」を表し、各イテレーションで部分列を 1 要素ずつ伸ばしていきます。手順は以下の通りです。

• m := 10^9 + 7(剰余演算用の定数)
• dp := nums と同じサイズのリストを作成し、すべて 1 で初期化
• 次の処理を k 回繰り返す:
  • j を dp のサイズ - 1 から 0 まで 1 ずつ減らしながら繰り返す:
    • dp[j] := 0
    • i を 0 から j - 1 まで繰り返す:
      • 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

計算量について

このアルゴリズムの時間計算量は O(k × n²)(n はリストの長さ)、空間計算量は O(n) です。n や k が大きい場合は、Binary Indexed Tree(BIT)などのデータ構造を使うことでさらに高速化することも可能です。