【C#】動的計画法(DP)を実装してみる - はなちるのマイノート

はじめに

今回は動的計画法(DP)を実装してみようという記事になります！

動的計画法とはなんだ一体というと、こんな感じ。

対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

動的計画法 - Wikipedia

かなりざっくりとした説明になりますが、そもそも動的計画法は抽象的なもので色々な種類があるようです。

ということで一番簡単？そうな箇所からみていきたいと思います。

はじめに
フィボナッチ数列
ボトムアップ方式
トップダウン方式
さいごに

フィボナッチ数列

動的計画法のよくある例としてフィボナッチ数列を求めるものがあります。

フィボナッチ数列とは以下のような式で表される数列のことです。

$F_0 = 0$
$F_1 = 1$
$F_{n+2} = F_n + F_{n+1} (n ≧ 0)$

f:id:hanaaaaaachiru:20200409163253p:plain

これを動的計画法を用いて実装してみます。

ボトムアップ方式

まずはボトムアップ方式といわれる方法を見ていきましょう。

public static long Fibonacci(long n)
{
    long[] dp = new long[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];
}

計算は0 -> 1 -> 2 -> ... -> nといった順番で行われ、それぞれを計算結果を記録(メモ)をしています。

計算量は $O(n)$ です。

トップダウン方式

次にトップダウン方式といわれる方法。

public static class Fibonacci
{
    private static long[] _dp = null;

    public static long Get(long n)
    {
        if (_dp == null) _dp = new long[n + 1];     // 初回のみインスタンス化
        if (n <= 0) return 0;
        if (n <= 2) return 1;
        if (_dp[n] != 0) return _dp[n];             // 計算したことがある値だったら再利用

        _dp[n] = Get(n - 1) + Get(n - 2);
        if (n == _dp.Length) _dp = null;            // 使い終わったメモは削除しておく
        return _dp[n];
    }
}