All lessonsOpen Open Open Open Open
11. DP, Greedy & Tries
Classic DP patterns
0 of 5 activities0%
Reading 1
Templates
1D DP: dp[i] from earlier indices (stairs, house robber). 0/1 knapsack: dp[item][capacity] or rolling 1D. LCS: 2D table on two strings.
Define state clearly: “what does dp[i] mean?” Then the transition.
// house robber sketch
dp[i]=max(dp[i-1], dp[i-2]+a[i]);Check 2
State
Before coding DP you should define
Fill in 3
Knapsack
Try it 4
Max of take/skip
Robber on [2,7,9].
main.cpp
Loading editor…
Output will appear here.
Assignment 5
Max of two choices
Read a b. Print max(a,b) — the core of many DP transitions.
main.cpp
Loading editor…