Dynamic Programming for Beginners. Part 1

Dynamic Programming has similarities with backtracking and divide-conquer in many respects. Here is how we generally solve a problem using dynamic programming. Split the problem into overlapping sub-problems. Solve each sub-problem recursively. Combine the solutions to sub-problems into a solution for the given problem. Don’t compute the answer to the same problem more than once.…

Dynamic Programming for Beginners. Part 2 (1-D)

Now that we are introduced to the concept of Dynamic Programming(DP) , let us start doing some real analysis . In this note I am going to conclude 1-D DP . ## ----------------------- ## Let us start of with a problem : Q. Given a number , find the different number of ways to write…