Dynamic Programming (DP) is a powerful technique used to solve complex problems by breaking them down into simpler overlapping subproblems, solving each subproblem just once, and storing the results for reuse.
In Java (or any programming language), DP is especially useful for optimization problems like Fibonacci numbers, Knapsack, or Longest Common Subsequence.
Let’s dive into a classic example: Fibonacci Sequence.
🧠 What is Dynamic Programming?
Instead of recalculating the same results multiple times (as in recursion), DP stores previously computed values — making your solution faster and more efficient.
Two main approaches:
- Top-Down (Memoization)
- Bottom-Up (Tabulation)
💻 Java Example: Fibonacci with Dynamic Programming
java
public class FibonacciDP {
// Function to compute the nth Fibonacci number using dynamic programming
public static int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
// Array to store Fibonacci numbers up to n
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
// Build up the solution iteratively
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci number at position " + n + " is: " + fibonacci(n));
}
}
📈 Output
arduino
Fibonacci number at position 10 is: 55
🔍 How It Works
✅ Subproblem Optimization
We avoid recalculating values by storing results in an array fib[].
🔁 Bottom-Up Build
We start from the base cases and work our way up to the desired value — ensuring every required value is calculated once and used efficiently.
📦 When to Use Dynamic Programming?
Use DP if:
- The problem can be broken down into smaller subproblems.
- Subproblems overlap (i.e., same problems recur).
- You can store solutions to avoid recomputation.
🧩 Real-World DP Problems
Here are some other famous problems solved using dynamic programming:
ProblemDescription🎒 Knapsack ProblemMaximize value with a weight constraint📚 Longest Common SubsequenceFind the longest sequence common in two sequences📐 Matrix Chain MultiplicationFind the most efficient way to multiply a chain of matrices🐸 Min Jumps / StairsCount ways to reach the top using steps (1, 2, …)🧩 Edit DistanceMinimum operations to convert one string to another
🔚 Summary
Dynamic Programming is a key strategy in any software engineer's toolbox. It takes advantage of overlapping subproblems and optimal substructure to build efficient solutions. Whether you’re solving Fibonacci numbers or building AI pathfinders, DP will likely show up.