Dynamic Programming Explained with Simple Animations

What is Dynamic Programming?Dynamic Programming is an algorithmic technique that solves complex problems by breaking them down into simpler overlapping subproblems.Unlike the Divide and Conquer approach, Dynamic Programming stores solutions to subproblems to avoid redundant calculations.Dynamic Programming is particularly useful when a problem exhibits two key properties.First, optimal substructure: This means that the optimal solution to the problem contains optimal solutions to its subproblems.Second, overlapping subproblems: This means that the same subproblems are solved multiple times when finding the solution to the original problem.Let's visualize how a problem gets decomposed into a tree of subproblems.A complex problem can be broken down into smaller subproblems.These subproblems can be further broken down into even smaller subproblems.And we continue this process until we reach the base cases.Notice how some subproblems appear multiple times in the tree. This is where the overlapping subproblems property comes into play.This is where memoization comes in. Instead of calculating the same subproblems multiple times, we store their solutions in a table.When we solve a subproblem for the first time, we calculate its result and store it in our memoization table.Then, whenever we encounter the same subproblem again, instead of recalculating, we simply look up the stored result from our table.This optimization technique drastically reduces the time complexity by avoiding redundant calculations, making Dynamic Programming an incredibly powerful approach for solving complex problems.