Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Fundamentals

Overlapping subproblems · a table you fill once
step 1 / 10
·
·
·
·
·
·
·
·
[0][1][2][3][4][5][6][7]
Tabulation (bottom-up)
▸
1dp = array of size n
2dp[0] = 0; dp[1] = 1          // base cases
3for i in 2..n−1:
4    // each subproblem solved once, then reused
5    dp[i] = dp[i−1] + dp[i−2]
6return dp[n−1]
state
  • recurrencedp[i] = dp[i−1] + dp[i−2]

line 1Dynamic programming solves a big problem by combining answers to smaller OVERLAPPING subproblems — and remembers each answer so it is never recomputed. The classic example: Fibonacci, where fib(i) = fib(i−1) + fib(i−2).