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 表格，高亮显示每个格子依赖的前置格子，并支持逐步操作。直接在浏览器中运行。
打开工具斐波那契数列可视化工具
动态演示斐波那契数列——每一项都是前两项之和，通过控制按钮逐步构建。直接在浏览器中运行。
打开工具汉诺塔模拟器
用递归算法求解汉诺塔问题的模拟工具——以最少 2ⁿ−1 步移动圆盘，支持单步执行。直接在浏览器中运行。
打开工具N 皇后可视化工具
动态演示回溯算法(backtracking)求解 N 皇后问题的过程——在棋盘上逐列尝试放置皇后、检测冲突、回溯撤销,并提供逐步执行的控制按钮。完全在浏览器中运行。
打开工具常见问题
N 皇后问题是什么?
在 n×n 棋盘上放置 n 个皇后,使得任意两个皇后都不会互相攻击——即不同行、不同列,也不在同一条对角线上。
回溯算法是如何求解这个问题的?
按列依次放置皇后。对每一列逐行尝试:如果某个位置安全,就递归进入下一列;如果所有行都不安全,就回溯并在上一列尝试其他行。
该算法的时间复杂度是多少?
最坏情况下约为 O(n!),但通过剪除冲突位置,实际运行中通常能更快地找到一个解。
哪些 n 值存在解?
除了 2 和 3 之外,其余所有 n 都存在解。经典的 8 皇后问题共有 92 种不同的解。