Dynamic Programming

Dynamic programming solves a problem by solving each overlapping subproblem once and reusing the answer, either top-down with a cache (memoization) or bottom-up by filling a table (tabulation).

In 1D DP, dp[i] is the answer for the first i elements (or position i), and it is built from a few earlier entries such as dp[i-1] and dp[i-2].

In grid DP each cell's answer comes from the neighbours you could have arrived from, usually the cell above and the cell to the left, filled row by row.

Knapsack DP tracks the best value for every capacity from 0 to W; looping capacities backwards uses each item once (0/1), looping forwards lets items repeat (unbounded).

Two-sequence DP fills a table where dp[i][j] answers the question for the first i characters of one string and the first j of the other, comparing the last characters at each step.

The longest increasing subsequence can be found in O(n^2) with dp[i] = longest run ending at i, or in O(n log n) by keeping the smallest possible tail for every length and binary searching it.