動的計画法 — Termwire

同じ計算を繰り返さないよう、一度解いた結果を覚えておきながら解く問題の解き方。

大きな問題を小さな問題に分解して解く点は再帰と似ているが、一度計算した小さな問題の答えを保存しておき、同じ計算を二度としない点が特徴。無駄な計算を大幅に減らせる。

素朴に再帰だけで解くと現実的な時間で終わらない問題も、この考え方を使うことで実用的な速さで解けるようになることがある。