Dynamic Programming
Dynamic Programming (DP) is a powerful algorithmic technique used to solve complex problems by breaking them down into simpler overlapping subproblems. This module covers the fundamentals of dynamic programming, common patterns, and applications in algorithm design.
Module Contents
Introduction to Dynamic Programming
Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems that exhibit the properties of overlapping subproblems and optimal substructure.
What is Dynamic Programming?
Dynamic Programming is both a mathematical optimization method and a computer programming method. In both contexts, it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.
When to Use Dynamic Programming
Dynamic Programming is useful when a problem has the following characteristics:
- Overlapping Subproblems: The problem can be broken down into subproblems which are reused several times.
- Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions of its subproblems.
Advantages of Dynamic Programming
- Reduces time complexity by avoiding redundant calculations
- Provides a systematic approach to solving optimization problems
- Can solve problems that would be infeasible with a naive recursive approach
Key Concepts
1. Overlapping Subproblems
A problem has overlapping subproblems if the same subproblems need to be solved multiple times when finding the solution to the original problem.
Example: Fibonacci Sequence
To calculate the nth Fibonacci number, we need to calculate the (n-1)th and (n-2)th Fibonacci numbers. This leads to many redundant calculations in a naive recursive approach.
// Naive recursive approach (inefficient)
public int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}2. Optimal Substructure
A problem has optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.
Example: Shortest Path
If the shortest path from A to C goes through B, then the path from A to B and the path from B to C must also be the shortest paths between those respective points.
3. Memoization
Memoization is a technique used in dynamic programming where we store the results of expensive function calls and return the cached result when the same inputs occur again.
Example: Memoized Fibonacci
// Memoized approach (efficient)
public int fibonacci(int n, int[] memo) {
if (memo[n] != 0) {
return memo[n];
}
if (n <= 1) {
return n;
}
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
// Usage
public int fib(int n) {
int[] memo = new int[n + 1];
return fibonacci(n, memo);
}4. Tabulation
Tabulation is a bottom-up approach to dynamic programming where we start from the smallest subproblems and work our way up to the original problem.
Example: Tabulated Fibonacci
// Tabulated approach (efficient)
public int fibonacci(int n) {
if (n <= 1) {
return 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];
}Approaches to Dynamic Programming
There are two main approaches to implementing dynamic programming solutions: top-down (memoization) and bottom-up (tabulation).
1. Top-Down Approach (Memoization)
The top-down approach starts with the original problem and recursively breaks it down into subproblems. It uses memoization to store the results of subproblems to avoid redundant calculations.
Advantages:
- More intuitive and follows the natural recursive structure of the problem
- Only computes the subproblems that are actually needed
- Easier to implement for some problems
Disadvantages:
- Recursive calls can lead to stack overflow for large inputs
- May have more overhead due to recursive function calls
2. Bottom-Up Approach (Tabulation)
The bottom-up approach starts with the smallest subproblems and iteratively builds up the solution to the original problem. It uses a table (array) to store the results of subproblems.
Advantages:
- Avoids recursive calls and potential stack overflow
- Generally more efficient in terms of time and space
- Can often be optimized to use less memory
Disadvantages:
- May compute subproblems that are not needed for the final solution
- Can be less intuitive to implement for some problems
Comparison: Solving the Fibonacci Sequence
Top-Down (Memoization)
// Top-down approach with memoization
public int fib(int n) {
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return fibMemo(n, memo);
}
private int fibMemo(int n, int[] memo) {
if (n <= 1) {
return n;
}
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}Bottom-Up (Tabulation)
// Bottom-up approach with tabulation
public int fib(int n) {
if (n <= 1) {
return 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];
}Common Patterns in Dynamic Programming
Dynamic programming problems often fall into several common patterns. Recognizing these patterns can help in developing solutions more efficiently.
1. 1D Array (Linear DP)
Problems where the state depends on previous states in a linear fashion.
Example: Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}2. 2D Array (Matrix DP)
Problems where the state depends on a 2D grid of previous states.
Example: Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// Fill first row
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// Fill first column
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// Fill rest of the dp table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}3. Interval DP
Problems where the state depends on intervals or subarrays.
Example: Palindromic Substrings
Given a string, count the number of palindromic substrings in it.
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
// All substrings of length 1 are palindromes
for (int i = 0; i < n; i++) {
dp[i][i] = true;
count++;
}
// Check for substrings of length 2
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
count++;
}
}
// Check for substrings of length 3 or more
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
count++;
}
}
}
return count;
}4. Knapsack Pattern
Problems involving selecting items with constraints to maximize or minimize an objective.
Example: 0/1 Knapsack
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.
public int knapsack(int[] values, int[] weights, int capacity) {
int n = values.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
values[i - 1] + dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}5. Longest Common Subsequence (LCS) Pattern
Problems involving finding common subsequences or substrings between sequences.
Example: Longest Common Subsequence
Given two strings, find the length of their longest common subsequence.
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}Classic Dynamic Programming Problems
Here are some classic dynamic programming problems that are frequently encountered in interviews and competitive programming.
1. Fibonacci Sequence
Calculate the nth Fibonacci number using dynamic programming.
The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.
2. Longest Increasing Subsequence
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [10, 22, 9, 33, 21, 50, 41, 60, 80] is 6 and the LIS is [10, 22, 33, 50, 60, 80].
3. Coin Change Problem
Given a set of coin denominations and a target amount, find the minimum number of coins needed to make up that amount.
For example, if the coins are [1, 5, 10, 25] and the amount is 30, the minimum number of coins needed is 2 (one 25-cent coin and one 5-cent coin).
4. Edit Distance
Given two strings, find the minimum number of operations required to convert one string to another.
The allowed operations are: insert a character, delete a character, or replace a character.
5. Matrix Chain Multiplication
Given a sequence of matrices, find the most efficient way to multiply these matrices together.
The problem is not to actually perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.
Practice Problems
Apply your knowledge of dynamic programming by solving these carefully selected problems:
1. Maximum Subarray Sum
Find the contiguous subarray within an array of numbers which has the largest sum.
2. Longest Palindromic Substring
Find the longest substring that is a palindrome within a given string.
3. Unique Paths
A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right. How many possible unique paths are there to the bottom-right corner?
4. House Robber
A professional robber plans to rob houses along a street. Each house has a certain amount of money stashed. The only constraint is that adjacent houses cannot be robbed. Determine the maximum amount of money the robber can rob.