Introduction to Dynamic Programming
What is Dynamic Programming ?
In the world of algorithm design, few techniques are as powerful and essential as Dynamic Programming (DP). Whether you’re preparing for coding interviews, solving competitive programming challenges, or building efficient software solutions, mastering DP can be a game changer.
At its core, dynamic programming is all about solving complex problems by breaking them down into simpler sub problems, and storing the solutions to avoid redundant computations.
About Dynamic Programming
Dynamic Programming (DP) is one of the most powerful techniques in computer science for solving optimization problems.
- It is a method used to solve complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations.
- From Fibonacci numbers to advanced graph algorithms, DP is a foundational concept every programmer must master.
It is particularly useful when a problem has the following properties:
- Optimal Substructure: The optimal solution of a problem can be constructed from the optimal solutions of its subproblems.
- Overlapping Subproblems: The problem can be broken down into subproblems which are reused several times.
Top Down vs Bottom Up Approaches
There are 2 primary approaches in DP:
1. Top Down (Memoization)
This approach uses recursion. We start solving the problem by breaking it into smaller subproblems and storing their results in a cache (usually an array or map) to avoid recomputation.
Code:
// Top-Down Fibonacci (Memoization)
public class FibonacciMemo {
static int[] dp = new int[1000];
static int fib(int n) {
if (n <= 1)
return n;
if (dp[n] != 0)
return dp[n];
dp[n] = fib(n - 1) + fib(n - 2);
return dp[n];
}
public static void main(String[] args) {
System.out.println(fib(10)); // Output: 55
}
}2. Bottom Up (Tabulation)
This approach solves all related subproblems first and uses their answers to build up solutions to bigger subproblems.
// Bottom-Up Fibonacci (Tabulation)
public class FibonacciTabulation {
static int fib(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];
return dp[n];
}
public static void main(String[] args) {
System.out.println(fib(10)); // Output: 55
}
}
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Types of Problems Solved Using Dynamic Programming
1. Fibonacci Numbers
Calculates the nth number in the Fibonacci sequence using previously computed values to avoid redundant recursion.
2. Knapsack Problem
Selects items with maximum value under a weight constraint—solved using 0/1 or fractional strategies.
3. Longest Common Subsequence (LCS)
Finds the longest sequence present in the same order in both strings (not necessarily contiguous).
4. Matrix Chain
Multiplication
Determines the most efficient way to multiply a chain of matrices by minimizing scalar multiplications.
5. Partition Problems
Decides whether an array can be divided into two subsets with equal sums or into parts with specific conditions.
6. Subset Sum
Checks if there’s a subset of a given set whose elements add up to a specific sum.
7. Coin Change
Finds the number of ways to make change or the minimum number of coins required for a given amount.
8. Edit Distance
Measures how many operations (insert, delete, replace) are needed to convert one string into another.
9. Rod Cutting
Maximizes profit by cutting a rod into pieces and selling them based on given prices.
10. Catalan Numbers
Solves combinatorial problems like valid parenthesis combinations, binary tree structures, etc.
Some Common Dynamic Programming Problems Explained
1. 0/1 Knapsack Problem
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
public class Knapsack01 {
static int knapsack(int[] wt, int[] val, int W, int n) {
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i - 1] <= w)
dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}
public static void main(String[] args) {
int[] wt = { 1, 3, 4, 5 };
int[] val = { 1, 4, 5, 7 };
int W = 7;
int n = wt.length;
System.out.println(knapsack(wt, val, W, n)); // Output: 9
}
}
Space Complexity: O(n*W)
2. Longest Common Subsequence (LCS)
Given two strings, find the length of the longest subsequence present in both.
DP Relation:
if (X[i] == Y[j])
dp[i][j] = 1 + dp[i-1][j-1]
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
public class LCS {
static int lcs(String X, String Y) {
int m = X.length(), n = Y.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X.charAt(i - 1) == Y.charAt(j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println(lcs("AGGTAB", "GXTXAYB")); // Output: 4
}
}
Space Complexity: O(m*n)
Memoization vs Tabulation in Dynamic Programming
| Criteria | Memoization | Tabulation |
|---|---|---|
| Style | Top-down (recursive) | Bottom-up (iterative) |
| Ease of Writing | Simpler, intuitive | More control over flow |
| Performance | Slightly more overhead (stack) | Usually faster |
| Memory Usage | Can be worse (due to recursion) | More predictable |
Use memoization for tree/graph DP, and tabulation when recursion depth might cause stack overflow or when optimization is required.
Common Dynamic Programming Problems and their Complexity
| Problem | Time Complexity | Space Complexity |
|---|---|---|
| Fibonacci (Basic) | O(n) | O(1) |
| 0/1 Knapsack | O(nW) | O(nW) |
| Longest Common Subseq. | O(mn) | O(mn) |
| Edit Distance | O(mn) | O(mn) |
| Matrix Chain Multip. | O(n^3) | O(n^2) |
| Subset Sum | O(n*sum) | O(n*sum) |
Real Life Applications of Dynamic Programming
- Route optimization in Google Maps
- Bioinformatics (DNA sequence alignment)
- Financial modeling and portfolio optimization
- Spell checkers using edit distance
- Game AI to find best move using DP
- Text Justification in document formatting
Tips for Solving DP Problems
- Recognize the problem type – Optimization or counting?
- Identify the recurrence – Try to express the relation between subproblems.
- Choose an approach – Top-down or Bottom-up.
- Think about space – Can you optimize?
- Trace your table – Backtrack to understand how values are built.
- Practice classic patterns – LCS, Knapsack, LIS, etc.
FAQ's related to Dynamic Programming
Answer:
Dynamic Programming is a method used in computer science to solve complex problems by breaking them down into simpler subproblems, solving each subproblem just once, and storing their results (usually using memoization or tabulation) to avoid redundant computations.
Answer:
Use DP when a problem has overlapping subproblems (solving the same subproblem multiple times) and optimal substructure (optimal solution can be formed using optimal solutions of subproblems).
Answer:
- Memoization is a top down recursive approach with caching.
- Tabulation is a bottom up iterative approach using a table to build the solution step by step.
Answer:
Some common DP problems include:
- Fibonacci Series
- 0/1 Knapsack
- Longest Common Subsequence
- Edit Distance
- Matrix Chain Multiplication
- Subset Sum
Answer:
No. While DP reduces time complexity significantly, it may use more space. It’s ideal only when the problem has overlapping sub problems and optimal substructure. For problems without these properties, other algorithms may be better.
