Recently I’ve attended a two-day workshop on “Dynamic Programming” under the mentorship of Mr. Vimal Daga Sir..!!

# Key Takeaways:

• TC of an algorithm determines the amount of time taken for an algorithm to run as a function of the length of its input
• whereas the SC of an algorithm determines the amount of space required for an algorithm
• Richard Bellman was the one to give the concept of DP for solving large mathematic computational problems
• In python we have a library called time_profiler, this produces the execution time info in steps
• Similarly for measuring SC we use the library memory_profiler
• In a multi-staged decision problem, the N variable problem is represented by N single variable problems
• These are solved in a cascade/successive approach in order to produce an optimal value from the original problem for getting optimal solution successively of each of these N single variable problems
• Such given problems have Optimal Substructure property, the solution for such a given problem is obtained by using the effective solutions of the sub-sequent problems
• Backward induction is the one in which the processor reasoning is done in backward (in time)
• it's done from the end of the problem, in order to determine an optimal approach
• Overlapping substructure problem is the one in which multiple sub-problems consist of the same approach
• The memorized program is similar to the recursion approach but with a small modification, it makes it look like a loop-up table before the solution is computed
• when a solution is needed to a subproblem, it reaches for the look-up table, when it finds a precomputed value suited, it’ll return it else it will calculate it
• understood its limitations :
• 1. slows down by a margin in initial execution.
• 2. very high memory usage.
• Merits: tabulation method won't take extra space in the stack, and consumes less time
• Demerits: consists of a complex decision-making process
• divide and conquer is the approach in which we divide a problem into subproblems to solve them individually, this has chances of coming across repetitive substructures
• A greedy Algorithm is the one in which the decision is taken in a step by assuming the solution is correct while not reconfirming it