Dynamic Programming
Memoization, recursion & DP — breaking problems into subproblems
Dynamic programming (DP) solves a hard problem by breaking it into overlapping subproblems and reusing their answers instead of recomputing them.
When does DP apply?
Two properties make a problem a DP candidate: optimal substructure (the best overall answer is built from best sub-answers) and overlapping subproblems (the same sub-answer is needed many times). The Fibonacci sequence is the textbook example — naive recursion recomputes the same values exponentially, while caching them makes it linear.
Top-down vs bottom-up
Memoization (top-down) keeps the natural recursion but caches each result the first time it is computed. Tabulation (bottom-up) fills a table from the smallest subproblems upward, often saving stack space. Both turn exponential work into polynomial work.
Recursion & backtracking
Classic teaching examples — the knapsack problem, the Tower of Hanoi and the N-Queens puzzle — show how recursion, memoization and backtracking relate. Step through them below to watch the recursion tree collapse once results are cached.
Try it interactively
ナップサック問題(0/1)ビジュアライザー
0/1ナップサック問題を動的計画法(dynamic programming)でアニメーション表示 — DPテーブルを1マスずつ埋めながら、依存関係にあるセルをハイライトし、ステップ実行にも対応。ブラウザ上でそのまま動作します。
ツールを開くフィボナッチ数列ビジュアライザー
フィボナッチ数列の生成過程をアニメーションで可視化 — 各項は直前の2項の和で、ステップごとの操作ボタンで一項ずつ組み立てられます。ブラウザ上ですぐに動作します。
ツールを開くハノイの塔シミュレーター
ハノイの塔問題を再帰的に解くシミュレーター — 最小手数2ⁿ−1で円盤を移動し、ステップごとに操作を確認できます。ブラウザ上でそのまま動作します。
ツールを開くN-Queensビジュアライザー
N-Queens問題をバックトラッキングアルゴリズムで動的に解く様子をシミュレーション — チェス盤上でクイーンを配置し、衝突を検出し、行き詰まると後戻りするプロセスをステップ操作ボタンで確認できます。ブラウザだけで完結。
ツールを開くよくある質問
N-Queens問題とは何ですか?
n×nのチェス盤にn個のクイーンを、どの2つも互いに攻撃し合わないように配置する問題です — 同じ行、同じ列、同じ対角線に置くことはできません。
バックトラッキングはこの問題をどのように解きますか?
列ごとに順番にクイーンを配置していきます。各列では行を1つずつ試し、その位置が安全なら次の列へ再帰的に進みます。安全な行が1つもなければ後戻りし、前の列で別の行を試します。
このアルゴリズムの時間計算量はどのくらいですか?
最悪ケースではおよそO(n!)ですが、衝突する配置を枝刈りすることで、実際にはずっと速く解が見つかります。
どのようなnの値で解が存在しますか?
2と3を除くすべてのnで解が存在します。定番の8クイーン問題には92通りの異なる解があります。