動的計画法

1. 定義

動的計画法とは、大きな問題を小さな部分問題に分けて解き、その答えを覚えておいて何度も使い回すことで、全体を効率よく解く方法のことです。

2. 仕組みと内訳

この方法が効くのは、次の2つが成り立つ問題です。

• 部分問題に分けられる: 大きな問題の答えが、小さな問題の答えから組み立てられます
• 同じ部分問題が何度も出てくる: 分けていくと、同じ計算が繰り返し現れます

素直に分けて解くと、同じ部分問題を何度も計算し直すことになります。その答えを一度計算したら記録しておき、次からは記録を読むのが動的計画法です。この記録するやりかたをメモ化と呼びます。

たとえば数列の n 番目を「前の2つの和」で定義して素直に計算すると、同じ位置の値を何度も計算し直します。記録を使えば、各位置につき1回だけ計算すれば済みます。

最適化問題を解く方法の1つとして置かれています。同じ並びには線形計画法・PERT・最短経路問題があります。