Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems and solving each of these subproblems just once, storing their solutions.

The idea is that once one of these subproblems is solved, the solution is stored, so if the same subproblem is encountered again, the answer can be looked up rather than recomputed.

This approach can significantly reduce the time complexity of algorithms that solve problems with overlapping subproblems.

.

Recursion, divide and conquer, and dynamic programming are three algorithmic strategies that can often be confused because they all involve breaking problems down into smaller pieces. However, each has distinct characteristics and uses cases.

.

Recursion

• Recursion is a technique where a function calls itself as a subroutine, allowing the function to operate on simpler or smaller pieces of the problem until it reaches a base case, which is directly solvable without further recursion.
• This method often leads to simple solutions that are easy to understand.
• However, it can be inefficient due to repeated calculations.
• A common example of recursion is in computing Fibonacci numbers, where each number is the sum of the two preceding ones, defined as F(n) = F(n-1) + F(n-2).

.

Divide and Conquer

• Divide and Conquer is an algorithm design paradigm based on multi-branched recursion.
• In this approach, a problem is divided into two or more subproblems that are similar to the original problem but smaller in size.
• Each of these subproblems is solved recursively, and their solutions are then combined to solve the original problem.
• This method ensures that each subproblem is solved independently, and solutions to subproblems are combined to create a solution to the original problem.
• An example of divide and conquer is Merge Sort, which divides the array into halves, recursively sorts each half, and then merges the sorted halves back together.

.

Dynamic Programming

• Dynamic Programming is used when a problem has overlapping subproblems. Instead of solving each subproblem from scratch, dynamic programming seeks to solve each subproblem only once, store its solution in a table (usually an array), and reuse the solution by looking it up when needed.
• This approach applies when the problem has overlapping subproblems and an optimal substructure.
• Solutions of subproblems are stored for future use and the approach can follow either a top-down (with memoization) or bottom-up method.
• An illustrative example is calculating Fibonacci numbers using a bottom-up approach, where previous results are stored and used to calculate subsequent ones without redundant computations.

.

History

In 1950, Richard Bellman (Who contributed in the Bellman Ford Algorithm) introduced the term “dynamic programming” in a RAND memorandum titled “Dynamic Programming and the Principle of Optimality.“

Bellman chose the term “dynamic programming” to avoid controversy and bureaucratic resistance, as “programming” was often associated with tabulating and planning military activities. The term “dynamic” emphasized the sequential or time-varying nature of the problems being addressed.

Despite its name, dynamic programming has nothing to do with programming in the sense of writing code; rather, it refers to a method of solving problems by breaking them down into simpler subproblems and solving each subproblem just once, storing their solutions.

.

How Dynamic Programming Works

Dynamic programming can be implemented using two main techniques

1. Top-Down Approach (Memoization) – This approach involves writing the recursive algorithm and then storing the results of the subproblems in a table (generally using a hash table or an array). Each time a subproblem is solved, the result is stored in this table, and subsequent requests for the solution check the table before computing the solution.
2. Bottom-Up Approach (Tabulation) – In this approach, the problem is solved by first looking at the smallest possible subproblems, solving those, and using their solutions to build up solutions to larger subproblems. This often involves filling up an n-dimensional table based on the recurrence relation that defines the problem.