Dynamic programming

less than 1 minute read

Dynamic Programming(DP)

Powerful algorithmic design technique
Large class of seemingly exponential problems have a polynomial solution via DP
Particularly for optimization problems(min/max) (e.g: shortest paths)

How to create a Dynamic Programming problems?

Find the first solution(base case)
Analyze the solution
Optimize the solution

Memoized DP Algorithm

memoized calls free(\(\theta(1)\) time)

Source

https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/pages/lecture-notes/