Dynamic Programming

Dynamic programming (DP) is a technique for solving problems by breaking them into overlapping subproblems, solving each subproblem once and storing the answer to reuse it. It turns many exponential-time recursive solutions into polynomial-time ones.

It applies when a problem has optimal substructure (the best answer is built from best answers to subproblems) and overlapping subproblems. Top-down DP (memoization) caches the results of recursive calls; bottom-up DP (tabulation) fills a table from the smallest cases upward. Classic DP problems are Fibonacci, the 0/1 knapsack, longest common subsequence and coin change.

// Bottom-up Fibonacci: O(n) instead of the O(2^n) naive recursion
static long fib(int n) {
	long[] dp = new long[n + 2];
	dp[1] = 1;
	for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
	return dp[n];
}