Dynamic Programming

Dynamic Programming — Part I

Algorithms #Algorithms #Dynamic Programming

Dynamic Programming — Lecture Notes 1. What Is Dynamic Programming? Dynamic programming (DP) is an algorithmic paradigm for solving problems that have overlapping subproblems and optimal substructure. Overlapping subproblems: the subproblems are smaller versions of the original problem. Optimal substructure: the optimal solution to a larger problem contains the optimal solutions to its smaller problems, so the larger problem can be derived from the smaller ones. 2. Example: Climbing Stairs A staircase has $n$ steps. Each move, you can climb 1 or 2 steps. How many distinct ways are there to reach the top?

Read note →

Memoization

Algorithms #Algorithms #Dynamic Programming #Memoization

Memoization 1. What Is Memoization? Memoization: a way of implementing a search that records information about states it has already visited, so that the same state is never traversed (recomputed) more than once. Memoization = DFS + an extra dictionary (cache) If the state has been searched before: look it up in the dictionary and return the stored result directly. If the state has not been searched before: keep searching, and finally record that state’s result into the dictionary. 2. Worked Example — Fibonacci Sequence Problem Define the Fibonacci sequence as:

Read note →