Introduction to Dynamic Programming

Dynamic Programming (DP) is a technique used to solve tricky problems in various fields. It shines when a problem involves making repeated calculations for the same smaller problem. Think of it like a shortcut. It helps us avoid doing the same work over and over again, saving us time and effort.

DP has a reputation for being a very difficult topic. In this book, we'll introduce you to Dynamic Programming through several problem walkthroughs, as this topic is best learned through practice.

The process of DP works in three phases:

• Break Down: We split a big, complicated problem into smaller, simpler problems that are easier to solve.
• Solve and Store: We solve each smaller problem and save the answer. This saved answer is like a completed puzzle section.
• Reuse Solutions: When we encounter the same smaller problem again, we don't have to solve it from scratch. We can reuse the answer we saved earlier.

Two Strategies

There are two main ways to approach a dynamic programming problem:

Top-Down (Memoization): The Recursive Approach

• Focus on the Original Problem: This approach begins by expressing the solution to the original, complex problem in terms of solutions to smaller subproblems.
• Recursive Breakdown: Breaks the problem down into smaller subproblems, often using a recursive function.
• Memoization for Efficiency: Stores the results of each solved subproblem. Before recomputing a subproblem, it checks if the solution is already stored and reuses it if available.

Bottom-Up (Tabulation): The Iterative Approach

• Solves in Order of Increasing Complexity: It typically starts by solving the smallest and simplest subproblems (often the base cases), then uses those solutions to solve progressively larger and more complex subproblems.
• Builds Up Solutions: It systematically constructs solutions for the subproblems using a table (often an array or a hashmap - object in JS). The table is filled in iteratively, with each entry representing the solution to a specific subproblem.
• Iterative Computation: Relies on loops (iteration) to fill in the table, avoiding the overhead of recursive function calls.

Time Complexity

Efficiency in dynamic programming (DP) problems can vary significantly depending on the implementation strategy. Without memoization, the complexity of solving DP problems can be exponential, often described as O(2^n), due to the need to recompute results for overlapping subproblems. However, when memoization is employed, the time complexity generally improves to O(N) if the problem has a linear number of states or O(N^2) if the problem states form a two-dimensional space. Both iterative and memoized recursive solutions share the same time complexity.

When to use DP

Dynamic Programming (DP) is particularly effective when solving problems that require optimizing specific criteria or accumulating results over several computations. This includes scenarios where you need to determine the minimum or maximum value, assess possibilities (true/false), optimize a particular outcome, calculate totals, or count distinct ways to achieve a goal.

Avoid DP When the problem asks for all possible solutions without optimization (use combinatorial techniques like backtracking instead).

DP vs DnC

DP might remind you of another problem-solving strategy called "divide and conquer." Both involve breaking a problem into smaller pieces. However, there's a key difference:

• Divide and Conquer: This focuses on dividing a problem into independent subproblems. You solve each subproblem once, combine the results, and you're done.
• Dynamic Programming: This is useful when subproblems overlap, meaning they share some common calculations. DP stores the results of these overlapping subproblems, preventing you from having to redo the same work multiple times.

In the following assignments, we'll use several problems to demonstrate how to solve them using DP, both top-down (recursively) and bottom-up (iteratively). Once you understand the solution for one approach, the other one will seem more manageable.