3.6.3 Dynamic Programming
Algorithms and Problem Solving
Dynamic Programming (DP) is an optimization technique used to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations. DP is particularly useful for problems with overlapping subproblems and optimal substructure.
Example: The Fibonacci sequence is a well-known example where DP can be applied. Instead of recalculating Fibonacci numbers repeatedly, DP stores the results of each Fibonacci number as it is computed, allowing the algorithm to retrieve these values directly when needed, significantly reducing the number of calculations.
Fibonacci sequence
The Fibonacci sequence is a series of numbers that starts with 0 and 1. Each subsequent number in the sequence is found by adding the two preceding numbers. Here's how it works:
- Start with 0 and 1.
- Add them together to get the next number: 0 + 1 = 1.
- Now add the last two numbers in the sequence: 1 + 1 = 2.
- Continue this pattern: 1 + 2 = 3, and so on.
So the Fibonacci sequence begins like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so forth. It is named after Leonardo of Pisa, who is also known as Fibonacci, and it appears in many interesting places in nature, such as the pattern of leaves on a stem, the branching of trees, and even the arrangement of a pine cone's scales.