All lessonsOpen Open Open Open Open
11. DP, Greedy & Tries
Dynamic programming intro
0 of 5 activities0%
Reading 1
Remember answers
DP solves problems by combining solutions to smaller subproblems, storing results so each subproblem is solved once.
Top-down: recursion + memo. Bottom-up: iterative table filling.
Classic: Fibonacci, climbing stairs, coin change, knapsack.
vector<int> memo;
int fib(int n){
if(n<=1) return n;
if(memo[n]!=-1) return memo[n];
return memo[n]=fib(n-1)+fib(n-2);
}Check 2
Key trait
DP needs overlapping subproblems and
Fill in 3
Table
Try it 4
Fib bottom-up
F(10).
main.cpp
Loading editor…
Output will appear here.
Assignment 5
Climbing stairs
Read n. Ways to climb n stairs taking 1 or 2 at a time = fib(n+1). Print it.
main.cpp
Loading editor…