Zenn
📌

【C#アルゴリズム】動的計画問題（DP）とは？

2024/11/15に公開
C#
競技プログラミング
動的計画法
tech

はじめに

競技プログラミングを進める中で動的計画問題というものがあったので解説します。
動的計画法 (Dynamic Programming, DP) とは、問題を部分問題に分割し、それらを解いていくことで元の問題の解を求める手法です。部分問題の結果を再利用することで、計算量を削減し、効率的に解を求めることができます。動的計画法にはボトムアップとトップダウンがありますが、今回は競技プログラミングでよく使われるボトムアップ方式についてコードを書いて説明しています。

動的計画法は、特に重複する部分問題が多い場合に有効です。再帰や単純な分割統治法では、同じ計算を何度も繰り返すことがあり、それが非効率な原因になります。動的計画法では、これらの部分問題の結果を利用して、重複する計算を避けることで高速化を実現します。

動的計画法の基本アイデア

  1. 問題を部分問題に分解する

    • 元の問題を、より小さな部分問題に分割します。
    • これらの部分問題は互いに独立していない場合が多く、部分問題の解が重複することがあります。

  2. 部分問題の結果を再利用する

    • 各部分問題の解を記録（メモ化）し、再度必要になったときに再利用します。
    • これにより、同じ計算を何度も繰り返さずに済みます。

  3. 最適な解を構築する

    • 記録した部分問題の解を組み合わせることで、元の問題の最適な解を得ます。

動的計画法のアプローチの種類

  • トップダウンアプローチ (Top-Down Approach):

    • 再帰 + メモ化 のスタイルです。
    • 最初に大きな問題を解こうとし、その過程で必要な部分問題を再帰的に解決します。
    • 各部分問題の解はメモ（キャッシュ）に保存し、再利用します。
    • この方法は競技プログラミングではあまり使用されません。

  • ボトムアップアプローチ (Bottom-Up Approach):

    • 反復処理（ループ）で解を求めるスタイルです。
    • 最も小さい部分問題から順に解いていき、結果をテーブルに保存し、最終的に元の問題の解を得ます。
    • こちらの方が一般的に再帰呼び出しのオーバーヘッドがなく、効率が良いです。

動的計画法の例

1. フィボナッチ数列

フィボナッチ数列は次のように定義されます:

F(n) = F(n-1) + F(n-2)\\ F(0) = 0, F(1) = 1

再帰のみの解法 (非効率)

// 非効率な再帰
int Fibonacci(int n)
{
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

この場合、ツリーは以下のようになります。


               Fibonacci(n)
              /            \
    Fibonacci(n-1)          Fibonacci(n-2)
        /      \                    /         \
Fibonacci(n-2) Fibonacci(n-3) Fibonacci(n-3) Fibonacci(n-4)
    ...

この方法は同じ計算を繰り返すため、計算量が O(2^n) と非常に非効率です。

C# での実装

// 効率的な動的計画法
int Fibonacci(int n)
{
    if (n <= 1) return n;
    
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

この方法では、各部分問題を1回ずつ解き、結果を再利用するため、計算量は O(n) となります。

2. 階段の上り方

問題の説明

  • n 段の階段があります。
  • 1 段または 2 段ずつ上ることができます。
  • n 段目に到達する方法の数を求めます。

漸化式の導出

フィボナッチ数列と違い、漸化式が与えられていませんので、その導き方を説明します。

  • n 段目に到達する方法は以下の 2 通りです：

    1. (n-1) 段目から 1 段上がる方法
    2. (n-2) 段目から 2 段上がる方法

  • よって、dp[n] は以下のように表せます：

dp[n] = dp[n-1] + dp[n-2]

初期条件

  • dp[0] = 1：0 段の階段にいる場合の方法は 1 通り（何もしない）。
  • dp[1] = 1：1 段目に到達する方法は 1 通り（1 段上がる）。

アプローチ

  1. 初期条件を設定します。
  2. 漸化式を使って dp テーブルを埋めていきます。
  3. 最後に dp[n] が答えになります。

C# での実装

using System;

class Solution
{
    static int ClimbStairs(int n)
    {
        // 0段または1段のときは、そのまま戻る
        if (n == 0) return 1;
        if (n == 1) return 1;

        // DP用の配列を準備
        int[] dp = new int[n + 1];
        
        // 初期条件
        dp[0] = 1; // 0段にいる方法は1通り（何もしない）
        dp[1] = 1; // 1段に上がる方法は1通り（1段上る）

        // 漸化式に基づいて dp テーブルを埋める
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // n 段目に到達する方法の数
        return dp[n];
    }

    static void Main(string[] args)
    {
        int n = 5; // 例として5段の階段
        Console.WriteLine($"{n}段の時、{ClimbStairs(n)}通りの上り方が存在します。");
    }
}

この方法では、各部分問題を1回ずつ解き、結果を再利用するため、計算量は O(n) となります。

3.最長増加部分列 (Longest Increasing Subsequence, LIS)

問題の説明

  • n 本の木が横一列に並んでいます。それぞれの木 i の高さは a[i] です。
  • 何本かの木を伐採して、残った木の高さが 単調増加 になるようにしたいと考えています。
  • 伐採されずに残る木の本数を最大にしたいです。

LIS (最長増加部分列) の定義

この問題は、与えられた配列 a の部分列のうち、要素が単調増加するものの長さが最大になる部分列を求めることと同じです。これを 最長増加部分列 (Longest Increasing Subsequence, LIS) と呼びます。

漸化式の導出

  • dp[i] を「木 i を最後の要素とする最長増加部分列の長さ」とします。
  • 配列 a の中から、部分列の長さを最大化するような dp[i] を求めるために、以下の関係式を利用します：
dp[i] = \max(dp[i], dp[j] + 1) \quad (0 \leq j < i \text{ かつ } a[j] < a[i])
  • つまり、木 j の高さが木 i より小さい場合、木 i を木 j の増加部分列に追加することで、dp[j] + 1 という新しい部分列を作れます。
  • その中で最長のものを選び、dp[i] として保存します。

初期条件

  • すべての i について、dp[i] = 1 とします。なぜなら、どの木も単独で長さ 1 の部分列になるからです。

アプローチ

  1. 初期条件を設定 します。
  2. 漸化式 に基づいて dp テーブルを埋めます。
  3. 最後に dp 配列の中の最大値が答えとなります。

C# での実装 (O(n^2) アプローチ)

using System;

class Solution
{
    static int LongestIncreasingSubsequence(int[] a)
    {
        int n = a.Length;
        int[] dp = new int[n];

        // 初期条件: すべての木は単独で長さ 1 の増加部分列
        for (int i = 0; i < n; i++)
        {
            dp[i] = 1;
        }

        // 漸化式に基づいて dp テーブルを埋める
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (a[j] < a[i])
                {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }

        // dp 配列の中の最大値が答え
        int result = 0;
        for (int i = 0; i < n; i++)
        {
            result = Math.Max(result, dp[i]);
        }

        return result;
    }

    static void Main(string[] args)
    {
        int[] heights = { 10, 20, 10, 30, 20, 50 }; // 例: 木の高さ
        Console.WriteLine("LIS の長さ: " + LongestIncreasingSubsequence(heights));
        // 出力: LIS の長さ: 4 (例: [10, 20, 30, 50])
    }
}

計算量

  • この実装の計算量は O(n^2) です。内部で二重ループが存在するため、配列の長さ n が増えると実行時間が増加します。

二分探索を利用した O(n log n) の解法

  • より効率的に解くために、二分探索 を用いて O(n log n) の時間で解くこともできますが、ここでは割愛します。
  • ヒント dp の代わりに、LIS を構築するための 補助配列 lis を用います。

4.部分和問題 (Subset Sum Problem)

問題の説明

  • n 個のおもりがあり、それぞれのおもり i の重さは a[i] です。
  • これらのおもりの中からいくつかを選んで、重さの和がちょうど x になるようにできるかどうかを判定してください。
  • ただし、同じおもりを2回以上選ぶことはできません。

DP テーブルの定義

  • dp[j] を「おもりの中からいくつか選んで、重さの和を j にすることができるかどうか」を表す真偽値とします。
    • dp[j] = true ならば、重さの和が j となるようにおもりを選ぶことが可能。
    • dp[j] = false ならば、重さの和が j となるように選ぶことは不可能。

漸化式の導出

  • おもり i を使うか使わないかの選択肢があります。

  • おもり i を使わない場合:

    dp[j] = dp[j] \, (\text{そのまま})

  • おもり i を使う場合:

    dp[j] = dp[j] \, \text{or} \, dp[j - a[i]]
    • ただし、j - a[i] >= 0 のときのみ有効です。

  • これにより、dp[j] は「dp[j - a[i]] が true であれば true になる」ため、おもり i を使うことで重さの和 j を作ることができるようになります。

初期条件

  • dp[0] = true：おもりを一つも選ばなければ、重さの和を 0 にすることは常に可能です。
  • それ以外の dp[j] は false で初期化します。

アプローチ

  • 2重ループを使用します。
    1. 初期条件を設定 します。
      　2. 漸化式 に基づいて dp テーブルを埋めます。
    2. 外側のループでおもり i を順に見ていきます。
    3. 内側のループは 重さ x から 0 まで逆順 で回し、dp 配列を更新します。
    • 逆順にすることで、おもり i を複数回選んでしまうことを防ぎます。
    1. dp[x]がTrueかFalseかを確認します。

C# での実装

using System;

class Solution
{
    static bool SubsetSum(int[] a, int n, int x)
    {
        // DP用の1次元配列を準備 (重さの和を0からxまで管理)
        bool[] dp = new bool[x + 1];
        dp[0] = true; // 初期条件: 重さの和を0にするのは常に可能

        // 各おもりについてループ
        for (int i = 0; i < n; i++)
        {
            // 重さの和を x から a[i] まで逆順で更新
            for (int j = x; j >= a[i]; j--)
            {
                if (dp[j - a[i]])
                {
                    dp[j] = true;
                }
            }
        }

        // 重さの和が x となる組み合わせが存在するか？
        return dp[x];
    }

    static void Main(string[] args)
    {
        // おもりの重さの配列
        int[] a = { 3, 2, 7, 1 };
        int n = a.Length;
        int x = 10;

        // 判定と出力
        if (SubsetSum(a, n, x))
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
}

実行結果

Yes

計算量

  • 時間計算量：O(n * x) です。
    • おもりの数 n に対してループを回し、その中で重さ x までのループを回すため。

動的計画法を使う際のポイント

  1. 最適部分構造:

    • 問題の最適な解が、その部分問題の最適解から構成されること。

  2. 重複部分問題:

    • 同じ部分問題が何度も計算される場合、それを記録して再利用できること。

まとめ

  • 動的計画法 は、部分問題を解いて結果を再利用することで、計算量を大幅に削減する手法です。
  • トップダウン（再帰 + メモ化）と ボトムアップ（反復処理）という2つのアプローチがあります。
  • 競技プログラミングやアルゴリズムの問題で頻繁に登場し、多くの最適化問題（ナップサック問題、最長共通部分列問題など）に適用可能です。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

Discussion