Solve a big problem by solving small versions first and writing the answers in a table.
The idea (do not redo your homework)
Say you are asked, “how many ways can I climb 30 stairs taking 1 or 2 steps at a time?” Instead of re-counting from scratch, notice: to stand on stair 30 you came from stair 29 or stair 28. So ways(30) = ways(29) + ways(28). If you write each answer in a table the first time you work it out, every later cell is just a quick look-up of cells you already have.
Every DP problem has the same recipe:
State: what does one cell mean? (e.g. “dp[i] = ways to climb i stairs”).
Base cases: the cells you know without thinking.
Transition: a formula that builds a cell from earlier cells. The yellow cells in the picture are exactly the cells the formula reads.
Order: fill so that the cells you need are always ready.
Answer: usually the last cell.
Watch it work
Try it
Stairs: try n = 10. The table is the Fibonacci sequence in disguise.
LCS: compare AGGTAB with GXTXAYB. When two letters match, which neighbor does the cell read?
LCS: try two strings with nothing in common. What does the table look like?
Knapsack: raise the capacity and watch which row-above cells get used when an item fits (“take it”) versus when it does not.
Common mistakes
Off-by-one in the table size. Make it n+1 by m+1 so the “empty” row/column 0 exists, and remember a[i-1] is the letter for row i.
Wrong fill order. A cell must only read cells that are already filled.
Mixing up “take” and “skip” in knapsack. Taking item i reads the row above at c - weight, not the same row (that would allow using an item twice).
Using plain recursion for overlapping problems. Without a table or memo, the same sub-problem is solved over and over, which can take exponential time.
Complexity, in plain English: work equals the number of cells, each filled in constant time. Stairs: O(n). LCS: O(m × n). Knapsack: O(items × capacity). The same recursion without a table could be exponentially slower.