1.6.7. Week 7: Dynamic Programming

When greedy does not work, we need a systematic way of exploring all the possibilities and choosing the best one. In this process, sometimes we have to discard overlapping problems and make sure that we do not waste fully recomputed things. So, this is covered by the concept of dynamic programming.

Dynamic programming is a method used to solve complex problems by breaking them down into simpler subproblems. It is applicable to problems that exhibit both optimal substructure (the optimal solution can be constructed from optimal solutions of its subproblems) and overlapping subproblems (subproblems recur many times). Dynamic programming provides a systematic approach to store the results of these subproblems, so we do not have to compute them multiple times, making our algorithms more efficient.

Imagine you're trying to climb a mountain. Each step represents a subproblem, and to reach the top (the optimal solution), you can take different paths (subproblems). Sometimes, taking a longer path might get you to the top more efficiently. However, if you retrace your steps every time instead of storing your previous paths, you will waste a lot of energy and time. Dynamic programming is similar; it helps us remember the best ways to climb those 'subproblem peaks' so we don't fall back into old paths unnecessarily.

In some cases, we can identify a strategy which looks at the local state of the problem and chooses an optimal path and arrives at the final solution without having to look at all possibilities.

Dynamic programming effectively narrows down the potential solutions to a problem by examining local options and making decisions that optimize the current solution. Unlike methods that explore every possible solution (like brute force), dynamic programming takes a more strategic approach. It carefully selects options based on previously calculated results, optimizing time and resources involved in solving the main problem.

Consider a chef preparing a large multi-course meal. Instead of starting from scratch for every dish (exploring all possibilities), the chef uses certain ingredients that are common across recipes. By prepping these ingredients first and using them in various ways, the chef saves time, reduces waste, and creates a more cohesive meal plan. This efficient use of shared resources mirrors how dynamic programming optimally solves complex problems.

Over the course of time, many generic techniques have been developed to solve the large number of problems. Among the techniques are divide and conquer, where we break up the problem into individual components which do not overlap with each other and then combine these solutions in order to get the solution for the overall problems. Dynamic programming is distinguished from divide and conquer by addressing overlapping subproblems.

Dynamic programming is commonly used for optimization problems. For instance, problems such as the Fibonacci sequence, shortest path problems (like Dijkstra's algorithm), and knapsack problems are solved efficiently using dynamic programming principles. These problems are characterized by overlapping subproblems, where the same computation can occur multiple times. By storing the solutions of these overlapping parts, dynamic programming enhances efficiency and reduces the computational load.

Think of dynamic programming as a puzzle with many overlapping pieces. Instead of trying to fit every piece separately, you recognize which pieces are part of multiple sections (like corner pieces in varying sections) and work on those first. By finding how pieces connect once instead of repeatedly (storing those connections), you can complete the puzzle much quicker.

--