Lecture 21 formulates stochastic sequential decisions as an MDP with known dynamics, defines value and Q-values through Bellman backups, and solves for an optimal policy with value or policy iteration.
Dynamic programming starts by defining subproblems, derives a recurrence from optimal substructure, and evaluates states in dependency order; Bellman–Ford layers by edge count, while Floyd–Warshall layers by allowed intermediate vertices.
Lecture 13 turns dynamic programming into five steps: choose a state, derive transitions, fill the table, reconstruct a solution, and then improve the implementation. LCS takes O(mn), both knapsack variants take O(nW) pseudo-polynomial time, and maximum-weight independent set on a tree takes O(|V|).