## Basic Concepts of Dynamic Programming

If this is your first time exploring this concept, it might feel a bit overwhelming, but we’ll show you two examples that will help you apply the two fundamental principles more concretely. These two basic principles include overlapping subproblems and optimal substructures.

Here is a comprehensive analysis:

### Overlapping Subproblems

When a particular mathematical solution involves solving the same problem multiple times, it has overlapping subproblems.

Dynamic programming optimizes data analysis by eliminating the process of calculating the same problem repeatedly by computing the solution once, storing the result, then reusing it as needed.

### Optimal Substructure

For dynamic programming to work, the problem must be such that it can be broken down into subproblems, and the solution to the whole problem is a combination of the solutions for each subproblem.

In that case, the initial problem has an optimal substructure.

### Example #1: The Fibonacci Sequence

The Fibonacci sequence is a frequently found pattern in nature and a mathematical concept that consists of a series of numbers in which each number is the sum of the two numbers before it. The first ten digits are 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55, in which 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, and so forth.

While solving the Fibonacci sequence with small numbers is simple, it gets more complicated as you move into larger and larger digits.

Dynamic programming, however, makes the process more straightforward by saving all previous computations and using them to calculate each proceeding one ad infinitum.

### Example #2: Change-Making Problem

Like the Fibonacci sequence, the Change-Making Problem is a mathematical and programming concept that requires figuring out the minimum number of coins of a particular denomination needed to make a given change.

So, for example, it might ask, “What is the minimum number of nickels, dimes, and pennies a cashier could use to give a customer exactly $0.36 in change?”

Typically, calculating the solution would require multi-step computations in which the solver multiplies various coins based on each denomination’s maximum total value without exceeding the maximum amount of change.

Dynamic programming eliminates that recursive process by storing the minimum number of coins needed for each smaller amount, then using it to solve more complex problems– such as $115.15 in change using quarters, nickels, dimes, and pennies– quickly and efficiently based on each previous problems’ solution.

You might also like: Best 12 Computer Programming Courses