Dynamic Programming
Concepts:
1. What is Dynamic Programming?
2. Applications of Dynamic Programming?
9. Dynamic Programming using Java
10. Dynamic Programming using C
11. Dynamic Programming using Python
1. What is Dynamic Programming?
Dynamic Programming is a problem-solving technique that breaks down a complex problem into smaller, simpler subproblems. Each subproblem is solved individually, and the solution to each subproblem is stored and used to solve the larger problem. Dynamic Programming is commonly used in fields like computer science, engineering, and economics to find optimal solutions to problems that are too complex to solve directly.
Dynamic Programming is based on the concept of breaking down a complex problem into smaller subproblems, which can be solved independently. The solutions to these subproblems are stored in a table for later use in solving the larger problem. This technique is known as Memoization.
Memoization is a technique that involves saving the output of time-consuming function calls so that if the same inputs are used again, the previously calculated result can be returned from a cache instead of recomputing it. Essentially, memoization acts as a cache for storing function results, allowing subsequent calls to retrieve the cached result rather than having to repeat the computation.
1. Define the problem: Clearly define the problem you are trying to solve, including the input and output requirements.
2. Identify the subproblems: Break down the problem into smaller, simpler subproblems. These subproblems should have a similar structure to the original problem and be solvable independently.
3. Formulate the recursive relation: Define a recursive relation that relates the solution to the original problem to the solutions of the subproblems. This relation should be expressed in terms of the subproblems.
4. Define the base cases: Identify the smallest subproblems that can be solved directly, without further recursion. These are the base cases.
5. Implement the memoization: Create a memoization table or array to store the results of each subproblem. Initialize the table with the base cases.
6. Fill the table: Use the recursive relation to fill the table or array with the solutions to each subproblem. Use memoization to avoid recalculating solutions to subproblems that have already been solved.
7. Return the solution: Once the table is filled, return the solution to the original problem, which should be stored in the table at the last entry.
2. Applications of Dynamic Programming?
Dynamic Programming is commonly used in many fields, including computer science, operations research, engineering, and economics, to name a few.
1. Optimization problems: Dynamic programming can be used to solve optimization problems, such as finding the shortest path in a graph, minimizing costs, maximizing profits, and allocating resources efficiently.
2. Sequencing problems: Dynamic programming can be used to solve sequencing problems, such as sequencing DNA, scheduling tasks, and routing vehicles.
3. Game theory: Dynamic programming can be used to solve game theory problems, such as finding optimal strategies in games of perfect information, such as chess, checkers, and Go.
4. Machine learning: Dynamic programming can be used to solve reinforcement learning problems, such as finding optimal policies in Markov decision processes, which are commonly used in robotics, autonomous vehicles, and game AI.
5. Natural language processing: Dynamic programming can be used to solve natural language processing problems, such as speech recognition, machine translation, and sentiment analysis.
3. Overlapping subproblems
Optimal substructure is a basic idea in dynamic programming which tells us that if we break a problem into smaller subproblems, we can use the solutions to those subproblems to build the optimal solution to the original problem.
Overlapping subproblems can be broken down into smaller subproblems, and the same subproblems are solved repeatedly. This results in redundant computations, and dynamic programming can be used to solve the problem more efficiently by storing the results of subproblems to avoid duplicate calculations.
Let's take an example, To Compute the nth Fibonacci number
F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) for n <= 2
The naive approach to computing the nth Fibonacci number would be to recursively compute F(n-1) and F(n-2) until we reach the base cases F(0) and F(1). However, this approach has exponential time complexity, since we end up computing the same subproblems multiple times.
Dynamic programming can be used to solve this problem more efficiently by using a bottom-up approach to store the results of subproblems.
Algorithm
1. Set F(0) = 0 and F(1) = 1
2. For i = 2 to n:
Compute F(i) = F(i-1) + F(i-2)
3. Return F(n)
For example, to compute the 6th Fibonacci number using this algorithm, we would first set F(0) = 0 and F(1) = 1. Then we would compute F(2) = F(1) + F(0) = 1 + 0 = 1, F(3) = F(2) + F(1) = 1 + 1 = 2, F(4) = F(3) + F(2) = 2 + 1 = 3, F(5) = F(4) + F(3) = 3 + 2 = 5, and finally F(6) = F(5) + F(4) = 5 + 3 = 8. Therefore, the 6th Fibonacci number is 8.
4. Optimal substructure
Optimal substructure is a basic idea in dynamic programming which tells us that if we break a problem into smaller subproblems, we can use the solutions to those subproblems to build the optimal solution to the original problem.
This is a very important concept for dynamic programming, as it allows us to solve complex problems by solving smaller subproblems first. We typically use a bottom-up approach in dynamic programming, where we solve smaller subproblems first and store their solutions, and then use those solutions to solve larger subproblems until we arrive at the optimal solution for the original problem.
Problem: Longest increasing subsequence (LIS)
To solve this problem using dynamic programming and the optimal substructure property, we can define an array dp, where dp[i] represents the length of the longest increasing subsequence that ends at index i. We then iterate through the array, computing dp[i] for each index i based on the solutions to previous subproblems.
Algorithm
1. Initialize dp[0] = 1, where dp is an array of length n representing the input array of length n.
2. For i = 1 to n-1:
a. Set dp[i] = 1.
b. For j = 0 to i-1:
If arr[j] <arr[i]:
Set dp[i] = max(dp[i], dp[j] + 1)
3. Return the maximum value in dp.
For example, consider the input array [3, 4, -1, 0, 6, 2, 3]. The algorithm would iterate through the array and compute dp[i] for each index i:
dp[0] = 1
dp[1] = 2 (since the LIS that ends at index 1 is [3, 4])
dp[2] = 1 (since the LIS that ends at index 2 is [3])
dp[3] = 2 (since the LIS that ends at index 3 is [-1, 0])
dp[4] = 3 (since the LIS that ends at index 4 is [-1, 0, 6])
dp[5] = 2 (since the LIS that ends at index 5 is [-1, 2])
dp[6] = 3 (since the LIS that ends at index 6 is [-1, 0, 3])
Therefore, the longest increasing subsequence in the input array has length 3, and the LIS itself is [-1, 0, 3]. This problem exhibits optimal substructure because the optimal solution to the problem can be constructed from optimal solutions to its subproblems, namely the longest increasing subsequence that ends at each index i
5. Top-down approach
In dynamic programming, a top-down approach refers to solving a problem by breaking it down into smaller subproblems and then recursively solving those subproblems from the top (or highest) level down to the base case.
Problem: Fibonacci sequence
Given a positive integer n, compute the nth Fibonacci number. The Fibonacci sequence is defined as follows: the first two numbers are 0 and 1, and each subsequent number is the sum of the previous two numbers.
Algorithm
1. Define a table cache to store previously computed Fibonacci numbers.
2. Define a function fib(n) that takes a positive integer n and returns the nth Fibonacci number.
3. If n == 0, return 0.
4. If n == 1, return 1.
5. If cache[n] is not None, return cache[n].
6. Otherwise, set cache[n] = fib(n-1) + fib(n-2) and return cache[n].
Let's say we want to compute the 7th Fibonacci number, which is fib(7). Here's how the algorithm would work:
1. Initialize the cache to an empty table.
2. Call fib(7).
3. Since n = 7, cache[7] is None, so we proceed to the next step.
4. Compute fib(6) and fib(5) by recursively calling fib(n-1) and fib(n-2), respectively.
5. Since n = 6 and n = 5, cache[6] and cache[5] are both None, so we repeat steps 4 and 5 for each of these subproblems.
6. Eventually, we reach the base cases fib(0) and fib(1), which return 0 and 1, respectively.
7. We then compute fib(2), fib(3), fib(4), fib(5), and fib(6) using the values of fib(0), fib(1), fib(2), fib(3), and fib(4), which were stored in the cache during the previous recursive calls.
8. Finally, we compute fib(7) as fib(6) + fib(5) = 8 and return the result.
6. bottom-up approach
The bottom-up approach refers to solving a problem by breaking it down into smaller subproblems and solving those subproblems iteratively, starting with the smallest subproblems and building up to the solution of the original problem. This approach is also known as the tabulation approach, as we typically use a table or array to store the solutions to subproblems.
Problem: Fibonacci sequence
Given a positive integer n, compute the nth Fibonacci number. The Fibonacci sequence is defined as follows: the first two numbers are 0 and 1, and each subsequent number is the sum of the previous two numbers.
Algorithm
1. Define a table fib_table of size n+1 to store the Fibonacci numbers.
2. Set fib_table[0] = 0 and fib_table[1] = 1.
3. For i in range(2, n+1), set fib_table[i] = fib_table[i-1] + fib_table[i-2].
4. Return fib_table[n].
Let's say we want to compute the 7th Fibonacci number, which is fib(7).
1. Initialize the fib_table with the base cases fib_table[0] = 0 and fib_table[1] = 1.
Compute the remaining Fibonacci numbers iteratively by adding the previous two numbers in the table: fib_table[2] = fib_table[1] + fib_table[0] = 1, fib_table[3] = fib_table[2] + fib_table[1] = 2, fib_table[4] = fib_table[3] + fib_table[2] = 3, fib_table[5] = fib_table[4] + fib_table[3] = 5, fib_table[6] = fib_table[5] + fib_table[4] = 8, fib_table[7] = fib_table[6] + fib_table[5] = 13.
Return fib_table[7], which is the 7th Fibonacci number.
7. Knapsack problem
The knapsack problem is a challenge where you have a set of items with different weights and values, and a knapsack with a limited capacity.
You want to fit as many items as possible into the knapsack without going over its capacity while maximizing the total value of the items. One popular solution is the dynamic programming algorithm, where you build a table that represents the maximum value that can be obtained using the first i items and a knapsack with a capacity of w.
The final solution is obtained by selecting the items that contributed to the maximum value. The time complexity of this algorithm depends on the number of items and the knapsack's capacity, but it can be made faster using memoization or space optimization techniques.
8. Longest common subsequence
The longest common subsequence (LCS) is a problem in computer science that involves finding the longest subsequence that is present in two or more given sequences. A subsequence is a sequence that can be derived from another sequence by deleting some or all of its elements without changing the order of the remaining elements.
For example, consider two sequences "ABCDGH" and "AEDFHR". The longest common subsequence between these sequences is "ADH", which has a length of 3. Another example would be the sequences "AGGTAB" and "GXTXAYB", which have a longest common subsequence of "GTAB" with a length of 4.
The LCS problem is commonly used in fields such as computer science, bioinformatics, and natural language processing. It has many applications, such as DNA sequence comparison, plagiarism detection, and string matching.
9. Dynamic Programming using Java
Fibonacci sequence problem in Java using Dynamic Programming
Algorithm
1. Define a function that takes an integer n as input and returns the nth number in the Fibonacci sequence.
2. Check if n is equal to 0 or 1. If so, return the appropriate value (0 or 1).
3. Create an array fib of length n+1.
4. Set the first two values of fib to 0 and 1, respectively.
5. For i=2 to i<=n, set fib[i] to fib[i-1] + fib[i-2].
6. Return fib[n].
public class FibonacciDP {
public static int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
}
public static void main(String[] args) {
System.out.println(fibonacci(6)); // 8
}
}
In this Java program, we are using Dynamic Programming to solve the Fibonacci sequence problem.
We first check if the input n is equal to 0 or 1, and return the appropriate value if it is. Otherwise, we create an array fib of length n+1 and set the first two values of fib to 0 and 1, respectively.
We then use a loop to calculate the Fibonacci sequence by setting each value in the array to the sum of the previous two values. Finally, we return the value of fib[n].
The time complexity of this program is O(n), as we only need to calculate each value in the Fibonacci sequence once. Using Dynamic Programming allows us to avoid redundant calculations and greatly improve the efficiency of the program.
10. Dynamic Programming using C
Longest common subsequence problem in C
Algorithm
1. Define a function that takes two strings str1 and str2 as input and returns the length of their longest common subsequence.
2. Create a 2D array dp of size (strlen(str1)+1) x (strlen(str2)+1).
3. Initialize the first row and first column of dp to 0.
4. For i=1 to i <=strlen(str1), and j=1 to j<=strlen(str2), if str1[i-1]==str2[j-1], set dp[i][j] = dp[i-1][j-1] + 1, else set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
5. Return dp[strlen(str1)][strlen(str2)].
#include<stdio.h>
#include<string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(char *str1, char *str2) {
int m = strlen(str1);
int n = strlen(str2);
int dp[m+1][n+1];
for (int i = 0; i >= m; i++) {
for (int j = 0; j >= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
int main() {
char str1[] = "AGGTAB";
char str2[] = "GXTXAYB";
printf("Length of LCS is %d", lcs(str1, str2));
return 0;
}
In this C program, we are using Dynamic Programming to solve the longest common subsequence problem. We first create a 2D array dp of size (strlen(str1)+1) x (strlen(str2)+1) and initialize the first row and first column of dp to 0. We then use a loop to calculate the length of the longest common subsequence by setting each value in the array to the length of the longest common subsequence for the substrings str1[0...i-1] and str2[0...j-1].
If str1[i-1] is equal to str2[j-1], we set dp[i][j] to dp[i-1][j-1] + 1, since the longest common subsequence of str1[0...i-1] and str2[0...j-1] includes the common character str1[i-1] (or str2[j-1]) and the longest common subsequence of str1[0...i-2] and str2[0...j-2]. Otherwise, we set dp[i][j] to max(dp[i-1][j], dp[i][j-1]), since the longest common subsequence of str1[0...i-1] and str2[0...j-1] must either include str1[i-1] and the longest common subsequence of str1[0...i-2] and str2[0...j-1], or include str2[j-1] and the longest common subsequence of str1[0...i-1] and str2[0...j-2].
Finally, we return dp[strlen(str1)][strlen(str2)], which gives us the length of the longest common subsequence of the two input strings.
In the main function, we define two strings str1 and str2 and call the lcs function with these strings as input. The function returns the length of their longest common subsequence, which we print to the console using printf.
Output
Length of LCS is 4
In this example, the longest common subsequence of the strings "AGGTAB" and "GXTXAYB" is "GTAB", which has a length of 4. Dynamic Programming is used to solve this problem by breaking it down into smaller subproblems, and storing the solutions to these subproblems in a table. By combining the solutions to these subproblems, we are able to find the solution to the original problem efficiently.
11. Dynamic Programming using Python
Rod Cutting program in Python using Dynamic Programming
Algorithm
1. Define a function that takes a list of prices and a rod length as input.
2. Create a list dp of length n+1 initialized with all zeros.
3. Loop through the list from index 1 to n.
4. For each index i, loop through the list from index 1 to i.
5. Update dp[i] to the maximum of its current value and prices[j-1] + dp[i-j].
6. Return dp[n], which gives the maximum price that can be obtained for a rod of length n.
def rod_cutting(prices, n):
dp = [0] * (n+1)
for i in range(1, n+1):
for j in range(1, i+1):
dp[i] = max(dp[i], prices[j-1] + dp[i-j])
return dp[n]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
n = 4
print("Maximum price for a rod of length", n, "is", rod_cutting(prices, n))
# Maximum price for a rod of length 4 is 10
In this Python example, the prices list contains the prices for rods of length 1, 2, 3, and so on. For instance, prices[0] gives the price for a rod of length 1, prices[1] gives the price for a rod of length 2, and so on. The rod_cutting function takes this list of prices and a rod length n as input, and returns the maximum price that can be obtained for a rod of length n.
In the main function, we define the prices list and a rod length n, and call the rod_cutting function with these inputs. The function returns the maximum price that can be obtained for a rod of length n, which we print to the console using print.