Pythonで全タスク完了までの最小時間を求めるプログラム（動的計画法）

数値のリスト nums が与えられ、各要素は対応するタスクを完了するのにかかる時間（単位時間）を表しています。このとき、連続しないタスクに限りスキップすることが許されます。ここでの目的は、すべてのタスクを完了するまでにかかる合計時間の最小値を求めることです。

例えば、入力が nums = [11, 6, 8, 16] の場合を考えてみましょう。この場合、最初と最後のタスクをスキップできるため、出力は 14 となります。

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

この問題は動的計画法を使って効率的に解くことができます。各タスクについて「そのタスクをスキップした場合」と「実行した場合」の2つの状態を管理し、それぞれの状態における最小コストを順次更新していきます。

具体的な手順は以下の通りです：

• n := nums のサイズとします
• table := n × 2 の行列を作成し、すべての要素を 0 で初期化します
• table[0, 0] := 0（最初のタスクをスキップした場合のコスト）
• table[0, 1] := nums[0]（最初のタスクを実行した場合のコスト）
• i を 1 から n - 1 まで繰り返します：
  • table[i, 0] := table[i - 1, 1]（現在のタスクをスキップするには、直前のタスクを実行している必要があるため）
  • table[i, 1] := min(table[i - 1, 0], table[i - 1, 1]) + nums[i]（現在のタスクを実行する場合は、直前の状態のうち小さい方に現在のタスクのコストを加えます）
• 最終行 table[n - 1] の最小値を返します

それでは、実際の実装を見て理解を深めましょう。

実装例

class Solution:
    def solve(self, nums):
        n = len(nums)
        table = [[0] * 2 for _ in range(n)]

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

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

        return min(table[n - 1])

ob = Solution()
nums = [11, 6, 8, 16]
print(ob.solve(nums))

入力

[11, 6, 8, 16]

出力

14

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。なお、DPテーブル全体を保持せず、直前の2つの状態だけを変数で管理すれば、空間計算量を O(1) に削減することも可能です。