dynamic programming
Last edited: November 11, 2025dynamic programming is a three-step algorithm to tackle large, multi-step problems; high level idea: guessing + caching + recursion. dynamic programming can sometimes not be good enough, and it doesn’t really give us fast enough to get what we need to use. That’s when we need to deal with relaxation, or possibly greedy programming.
constituents
optimal sub-structure
- big problems break up into sub-problems
- optimal solutions can be explained in terms of sub-problems solution
overlapping sub-problems
- many different entries of each solution use the same sub-problem answer
- …meaning,
requirements
bottom-up approach
- initialize a table
- fill it
top-down approach
- do the recursive approach
- memoize problem solutions during recursive call
additional information
main steps of dynamic programming
- Break a hard problem into sub-problems
- Guess what sub-problem to solve
- Solve the sub-problem and store the solution
- Repeat #2 and #3
- Combine sub-problem solutions to solve the hard problem
analyzing runtime of dynamic programming
To analyze runtime of dynamic programming problems, you ask:
greedy algorithm
Last edited: November 11, 2025Make choices one at a time, never look back.
when does one greedy?
When problem exhibit a particularly nice optimal substructure: “at every step, when we make a choice, we do not rule out an optimal solution; when we get to the end, we got a solution, and thus it must be optimal.” After we made all of our choices, if we haven’t ruled out an optimal solution, we would have found an optimal solution.
knapsack
Last edited: November 11, 2025unbounded knapsack
Suppose I have infinite copies of all items, what’s the most valuable way to fill the knapsack?
DP, with subproblems containing smaller knapsack. K[x] = max_i { K[x-wi] + vi }
def solve():
dp[0] = 0
sol[0] = []
for x in 1 ... knapsack_size:
dp[x] = 0
for i in 1 ... num_items:
if weight(i) <= x:
# why max base case instead of incrementally adding stuff?
# a bigger knapsack that fits 2 things can be find a sa
dp[x] = max(dp[x], dp[x-weight(i)]+value(i))
if dp[x] changed:
sol[x] = sol[x-weight(i)] + [i]
0/1 knapsack
Suppose I have one copy of each item; what’s the most valuable way to fill the knapsack? We have to keep track of a 2D DP table. Casework:
longest common subsequence
Last edited: November 11, 2025BDFH is a subsequence of ABCDEFGH. Given two lists, what’s the longest common subsequence?
optimal substructure
We consider sub problems’ of finding LCS of prefixes \(C[i,j]\). Casework:
C[i,j] = …
- for A[i] = B[j], then C[i,j] = C[i-1, j-1] + 1
- for A[i] != B[j] = max(C[i,j-1], C[i-1,j])
- if i=0 or j=0, then 0
Filling this table is \(O\qty(nm)\), and backtracing takes \(O\qty(n+m)\).
Machine Learning Index
Last edited: November 11, 2025Course Project
- Deliverables: proposal (300-500 words), milestone (3 pages), final report (5 pages), poster
- Evaluation: technical quality, originality, community