Dynamic Programming と Greedy

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

Dynamic ProgrammingとGreedyは大きな問題を小さな選択に分けるが、選択を扱う方法が違う。

Dynamic Programming

同じ小さな問題が繰り返され、小さな問題の最適解で大きな問題の最適解が作れる場合に使用する。

int Fibonacci(int N)
{
    if (N <= 1)
    {
        return N;
    }

    std::vector<int> DP(N + 1, 0);
    DP[1] = 1;

    for (int i = 2; i <= N; ++i)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
    }

    return DP[N];
}

計算した結果を保存するので、同じ再帰問題を繰り返さない。 状態定義と点火式を正しく立てることが核心だ。

Greedy

現在の瞬間に最も良く見える選択をし、以前の選択を元に戻さない。

活動選択問題のように終了時間が最も早い作業を続けていけば最適解になる問題がある。 しかし、コインユニットがランダムに与えられた粗い問題では、最大のコインから選ぶ方法は最適ではないかもしれません。

コイン: 1, 3, 4
金額：6

Greedy: 4 + 1 + 1 = 3個
最適解: 3 + 3 = 2つ

Greedyは高速でメモリを少なく使うが、地域最適選択が全体最適解につながるという証明が必要だ。 いくつかの例が当てはまるだけでGreedyを選択すると、反例で失敗します。