dynamic-programming
4 free lessons tagged dynamic-programming across Computer Science, AI. Each one is a short sequence of focused steps with narration and a five-question quiz at the end — take them in any order, no signup required.
Which Technique Applies, and How to Tell
A procedure for deciding between greedy, dynamic programming, and neither. Write the recurrence, count the states, attempt the greedy proof, and read the failure. Includes the instance where greedy is optimal and off by a third depending on one word in the problem statement.
Designing a Dynamic Program: State, Transition, Order
Writing a dynamic program is three decisions, not a recurrence to memorise. This lesson works through choosing the state, deriving the running time from it, fixing the evaluation order, recovering the answer rather than its value, and why an O(nW) knapsack is not polynomial.
Optimal Substructure: The Property Both Techniques Need
Dynamic programming and greedy algorithms both rest on a structural property the problem either has or does not have. This lesson establishes it precisely, shows a problem that lacks it, and separates the three properties that decide which technique applies.
Dynamic Programming: Value and Policy Iteration
When you know the full MDP model, dynamic programming finds the optimal policy exactly. Learn the Bellman optimality equation, the contraction argument that guarantees convergence, and the concrete difference between policy iteration and value iteration — with a value-iteration code walkthrough.