Pythonで解く！連続する3要素の各グループから1つ以上を選ぶ最小合計部分列の求め方

問題の概要

数値のリスト nums が与えられたとき、連続する3つの数値からなるどのグループにも、選んだ要素が少なくとも1つ含まれるという条件を満たす中で、合計が最小になる部分列（サブシーケンス）を見つける問題です。リストの長さが3未満の場合でも、少なくとも1つの要素は選択する必要があります。

具体例で理解する

たとえば、入力が nums = [2, 3, 4, 5, 6, 7] の場合を考えてみましょう。「2」と「5」を選ぶと、3連続のグループ [2, 3, 4]、[3, 4, 5]、[4, 5, 6]、[5, 6, 7] のすべてに選択要素が含まれ、合計は 2 + 5 = 7 になります。これよりも小さい合計で条件を満たす選び方は存在しないため、答えは 7 となります。

解法のアプローチ：動的計画法（DP）

この問題は、動的計画法を使うことで効率的に解くことができます。手順は以下のとおりです。

1. n をリスト nums のサイズとする
2. n == 0 の場合は 0 を返す
3. n == 1 の場合は nums[0] を返す
4. n == 2 の場合は nums[0] と nums[1] の小さい方を返す
5. 長さ n の配列 table を 0 で初期化して作成する
6. table[0] = nums[0]、table[1] = nums[1]、table[2] = nums[2] を設定する
7. i が 3 から n - 1 までの範囲で、table[i] = nums[i] + min(table[i-3], table[i-2], table[i-1]) を計算する
8. res = min(table[n-1], table[n-2], table[n-3]) を求める
9. res を返す

なぜこのDPで正しい答えが得られるのか

table[i] は「i 番目の要素を必ず選ぶ」という前提のもとで、そこまでの条件を満たす最小合計を表しています。要素 i を選んだとき、その直前に選んだ要素は i-1、i-2、i-3 のいずれかでなければなりません。i-4 以前しか選んでいないと、i-3、i-2、i-1 の3連続グループに選択要素が存在しなくなり、条件に違反するからです。

また、最終的な答えが末尾の3要素 table[n-1]、table[n-2]、table[n-3] の最小値になるのは、部分列の最後の要素が必ずリスト末尾から3つ以内の位置にあるためです。

Pythonでの実装例

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return min(nums[0], nums[1])
        table = [0] * n

        table[0] = nums[0]
        table[1] = nums[1]
        table[2] = nums[2]

        for i in range(3, n):
            table[i] = nums[i] + min(table[i - 3], table[i - 2], table[i - 1])

        res = min(table[n - 1], table[n - 2], table[n - 3])
        return res

ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

入力

[2, 3, 4, 5, 6, 7]

出力

7

計算量とまとめ

このアルゴリズムはリストを一度走査するだけで済むため、時間計算量 O(n)、DPテーブルの分だけ空間計算量 O(n) で処理できます。単純な貪欲法では局所最適に陥る可能性があるため、「各位置を末尾とする最小コスト」を段階的に積み上げていく動的計画法が有効なアプローチとなります。