Dynamic Programming

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial. For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.

This weekend had an amazing workshop on 𝕯𝖞𝖓𝖆𝖒𝖎𝖈 𝕻𝖗𝖔𝖌𝖗𝖆𝖒𝖒𝖎𝖓𝖌 where I learnt the following things:

1. Concept and importance of space complexity
2. What is Dynamic Programming
3. Multi stage decision process
4. ️Principle of Optimality
5. Overlapping structure problem
6. Backward induction
7. Optimal substructure
8. Algorithms
9. Time complexity and its effects
10. ️Memory profiler
11. ️Top down method / Memoization
12. Bottom up method / Tabulation