13.3.4. Dynamic Programming

Dynamic Programming (DP) is used to solve problems by breaking them into overlapping sub-problems. It stores the results of sub-problems to avoid recomputing them.

Dynamic Programming (DP) is a method used to solve complex problems by breaking them down into simpler, smaller sub-problems. The key aspect of dynamic programming is that these sub-problems overlap, meaning the same sub-problems are solved multiple times during the computation. DP stores the results of these solved sub-problems in a data structure (like an array) so that when the same sub-problem needs to be solved again, we can use the pre-computed result instead of recalculating it. This significantly reduces computation time and improves efficiency.

Imagine you are trying to climb a staircase with a certain number of steps. If you calculate the number of ways to reach each step individually, you may find yourself calculating the same values repeatedly (like the number of ways to get to step 2 while calculating for step 3). Instead, you can store the number of ways to get to each step as you calculate them, so whenever you need that information again, you simply look it up. This is similar to how dynamic programming works.

A common example is solving the Fibonacci Sequence. The Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

The Fibonacci sequence is a classic example to illustrate dynamic programming. The sequence starts with 0 and 1, and every subsequent number is the sum of the two preceding numbers. For instance, F(2) = F(1) + F(0) = 1 + 0 = 1, F(3) = F(2) + F(1) = 1 + 1 = 2, and so forth. When calculating this sequence recursively, it can lead to repeated calculations of the same Fibonacci numbers, leading to inefficiencies. By using dynamic programming, we can store results of each Fibonacci number in an array so that when we need F(n), we can quickly retrieve F(n-1) and F(n-2) without re-computing them.

Think of the Fibonacci sequence as a family tree where each generation has a number of offspring equal to the sum of the offspring of the two previous generations. Instead of starting from scratch to count each time a new generation arises, we can keep track of how many offspring each generation has produced, which allows us to quickly calculate future generations without unnecessary recalculations.

Example:

public class Fibonacci {
public static int fibonacci(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // Store the result of sub-problems
}
return dp[n];
}
public static void main(String[] args) {
int n = 6;
System.out.println("Fibonacci of " + n + " is: " + fibonacci(n)); // Output: 8
}
}

Time Complexity: O(n)

The provided code demonstrates how to implement the Fibonacci sequence using dynamic programming in Java. The fibonacci method creates an array to store the Fibonacci numbers from 0 to n. It initializes the first two positions of the array as F(0) = 0 and F(1) = 1. The method then uses a loop to fill in the rest of the array by adding the last two Fibonacci numbers. Finally, the function returns the nth Fibonacci number, which is accessed in constant time since it has already been calculated and stored. The time complexity of this algorithm is O(n) because we only compute each Fibonacci number once.

Imagine this code as a recipe for baking a layered cake. Instead of baking each layer from scratch every time you want to serve a slice, you prepare and store each layer once. Then, when it’s time to serve a specific number of layers, you simply retrieve them from storage rather than recooking everything.

--