1. Introduction
Dynamic programming is typically used to optimize recursive algorithms because they tend to scale exponentially. The main idea of dynamic programming is to break down complex problems (with many recursive calls) into smaller sub-problems and then store them in memory so that we don’t have to recalculate them every time we use them.
To understand the concept of dynamic programming, we need to be familiar with some topics:
- What is dynamic programming?
- Greedy algorithm
- Simplifying the backpack problem
- The traditional backpack problem
- Levenshtein Distance
- LCS- longest common subsequence
- Other problems using dynamic programming
- conclusion
All code in this article is implemented in Java code.
2. What is dynamic programming?
Dynamic programming is a programming principle that can be solved by dividing very complex problems into smaller subproblems. This principle is similar to recursion, but with the key difference that each different subproblem can be solved only once.
To understand dynamic programming, we first need to understand the problem of recursive relations. Each individual complex problem can be divided into small sub-problems, which means that we can construct a recursive relationship between these problems. Let’s take a look at a familiar example: The Fibonacci sequence, whose definition has the following recursion:
Fibonacci
So, if we want to find the NTH number in the Fibonacci sequence, we have to know the first two numbers of the NTH number in the sequence.
However, every time we want to calculate different elements of the Fibonacci sequence, we have some repeated calls in the recursive call, as shown in the figure below, and we calculate Fibonacci (5) :
For example, if we want to compute F(5), it is obvious that we need to compute F(3) and F(4) as prerequisites for computing F(5). However, in order to compute F(4), we need to compute F(3) and F(2), so we need to compute F(2) and F(1) to get F(3), and so on.
This results in a lot of repeated calculations, which are redundant in nature and significantly slow down the efficiency of the algorithm. To solve this problem, we introduce dynamic programming.
In this approach, we model the solution as if we were solving it recursively, but we solve it from scratch, memorizing the solution to the subproblem (substep) taken to get to the top. Thus, for Fibonacci sequences, we first solve and memorize F (1) and F (2), then compute F (3) using two memory steps, and so on. This means that each individual element in the sequence evaluates to O (1), because we already know the first two elements.
When using dynamic programming to solve a problem, we generally use the following three steps:
- Determine a recursive relationship that applies to the problem
- Initializes the initial value of memory, array, and matrix
- Make sure that it is always resolved in advance when we make recursive calls that have access to the answer to the subproblem.
Following these rules, let’s look at an example of an algorithm that uses dynamic programming:
3. Greedy algorithms
Take this as an example:
Given a rod of length n and an array that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
Copy the code3.1. Inexperienced developers may do the following
This problem is actually tailor-made for dynamic programming, but since this is our first real example, let’s see how many problems we encounter running this code:
public class naiveSolution {
static int getValue(int[] values, int length) {
if (length <= 0)
return 0;
int tmpMax = -1;
for (int i = 0; i < length; i++) {
tmpMax = Math.max(tmpMax, values[i] + getValue(values, length - i - 1));
}
return tmpMax;
}
public static void main(String[] args) {
int[] values = new int[]{3, 7, 1, 3, 9};
int rodLength = values.length;
System.out.println("Max rod value: "+ getValue(values, rodLength)); }}Copy the codeOutput result:
Max rod value: 17
This solution, while correct, is very inefficient, and the results of the recursive calls are not saved, so bad code has to solve the same subproblem every time there is an overlapping solution.
3.2. Dynamic approach
Using the same basic principles above, adding memorization and eliminating recursive calls, we get the following implementation:
public class dpSolution {
static int getValue(int[] values, int rodLength) {
int[] subSolutions = new int[rodLength + 1];
for (int i = 1; i <= rodLength; i++) {
int tmpMax = -1;
for (int j = 0; j < i; j++)
tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);
subSolutions[i] = tmpMax;
}
return subSolutions[rodLength];
}
public static void main(String[] args) {
int[] values = new int[]{3, 7, 1, 3, 9};
int rodLength = values.length;
System.out.println("Max rod value: "+ getValue(values, rodLength)); }}Copy the codeOutput result:
Max rod value: 17
As we can see, the output is the same, but the difference is the time and space complexity.
By solving subproblems from scratch, we eliminate the need for recursive calls, taking advantage of the fact that all previous subproblems of a given problem have been solved.
Performance improvement
To give evidence for the idea that dynamic approaches are more efficient, let’s try to run the algorithm with 30 values. An algorithm takes about 5.2 seconds to execute, while the dynamic solution takes about 0.000095 seconds to execute.
4. Simplifying the backpack problem
The simplified knapsack problem is an optimization problem without a solution. The question to this question is – “Does the solution exist?” :
Given a set of items, each with a weight w1, w2... determine the number of each item to put in a knapsack so that the total weight is less than or equal to a given limit K.
Given a group of items, each item weighs w1, w2…… Determine the amount of each item to put into the backpack so that the total weight is less than or equal to the given limit K
First let’s re-store the element ownership in the W array. Next, suppose there are n items, and we will enumerate them using numbers from 1 to n, so the ith item has a weight of W [I]. We’re going to form a matrix M with n plus 1 x K plus 1 dimensions. M [x] [y] corresponds to the solution to the knapsack problem, but includes only the first X entries of the start array, and has a maximum capacity of Y
For example,
Suppose we have three elements with weights w1=2kg,w2=3kg, and w3=4kg. Using the above method, we can say that M [1] [2] is an effective solution. This means we are trying to fill a 2kg backpack with the first item in the weight array (W1).
In M [3] [5], we tried to use the first three items of the weight array (W1, W2, W3) to fill a backpack with a capacity of 5kg. This is not an effective solution because we overfit it.
4.1. Matrix initialization
There are two things to note when initializing a matrix:
Does a solution exist for the given subproblem (M[x][y].exists) AND does the given solution include the latest item added to the array (M[x][y].includes).
Give the stator problem whether there is a solution (M [x] [y].exists) and the given solution includes the latest item added to the array (M [x] [y].includes).
Therefore, initializing the matrix is fairly easy, M[0][k].exists is always false if k>0, because we don’t put anything in a knapsack with k capacity.
On the other hand, M[0][0].exists = true, when k=0, the backpack should be empty, so we don’t put anything in it, this is a valid solution.
In addition, we can say M[k][0].exists = true, but for each K M[k][0].includes = false.
Note: Just because a solution exists for a given M [x] [y], it does not necessarily mean that that particular combination is a solution. In the case of M [10] [0], there is a solution that does not include any of the 10 elements. This is why M [10] [0].exists = true but M [10] [0].includes = false.
4.2. Algorithm principles
Next, let’s construct a recursive relation for M [I] [k] using the following pseudocode:
if (M[i-1][k].exists == True):
M[i][k].exists = True
M[i][k].includes = False
elif (k-W[i]>=0):
if(M[i-1][k-W[i]].exists == true):
M[i][k].exists = True
M[i][k].includes = True
else:
M[i][k].exists = False
Copy the codeTherefore, the point of the solution is to divide the subproblem into two cases:
- For capacity
kWhen there is the first onei-1Element solution - For capacity
k-W [i]Be the firsti-1The element has a solution
The first case is self-evident, we already have a solution to the problem.
The second case is where we know the solution for the first i-1 element, but only the i-th element is not enough, which means we can add an i-th element, and we have a new solution!
4.3. To achieve
To make things easier, we create a class Element to store elements:
public class Element {
private boolean exists;
private boolean includes;
public Element(boolean exists, boolean includes) {
this.exists = exists;
this.includes = includes;
}
public Element(boolean exists) {
this.exists = exists;
this.includes = false;
}
public boolean isExists() {
return exists;
}
public void setExists(boolean exists) {
this.exists = exists;
}
public boolean isIncludes() {
return includes;
}
public void setIncludes(boolean includes) { this.includes = includes; }}Copy the codeNext, we can dive into the main classes:
public class Knapsack {
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
System.out.println("Insert knapsack capacity:");
int k = scanner.nextInt();
System.out.println("Insert number of items:");
int n = scanner.nextInt();
System.out.println("Insert weights: ");
int[] weights = new int[n + 1];
for (int i = 1; i <= n; i++) {
weights[i] = scanner.nextInt();
}
Element[][] elementMatrix = new Element[n + 1][k + 1];
elementMatrix[0][0] = new Element(true);
for (int i = 1; i <= k; i++) {
elementMatrix[0][i] = new Element(false);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
elementMatrix[i][j] = new Element(false);
if (elementMatrix[i - 1][j].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(false);
} else if (j >= weights[i]) {
if (elementMatrix[i - 1][j - weights[i]].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(true); } } } } System.out.println(elementMatrix[n][k].isExists()); }}Copy the codeThe only thing left is the reconstruction of the solution, and in the class above, we know that the solution exists, but we don’t know what it is.
To rebuild, we use the following code:
List<Integer> solution = new ArrayList<>(n);
if (elementMatrix[n][k].isExists()) {
int i = n;
int j = k;
while (j > 0 && i > 0) {
if (elementMatrix[i][j].isIncludes()) {
solution.add(i);
j = j - weights[i];
}
i = i - 1;
}
}
System.out.println("The elements with the following indexes are in the solution:\n" + (solution.toString()));
Copy the codeOutput:
Insert knapsack capacity:
12
Insert number of items:
5
Insert weights:
9 7 4 10 3
true
The elements with the following indexes are in the solution:
[5, 1]
Copy the codeA simple variation of the knapsack problem is to fill knapsacks without value optimization, but now each individual item has an unlimited number.
This change can be addressed by a simple tweak to the existing code:
// Old code for simplified knapsack problem
else if (j >= weights[i]) {
if (elementMatrix[i - 1][j - weights[i]].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(true);
}
}
// New code, note that we're searching for a solution in the same
// row (i-th row), which means we're looking for a solution that
// already has some number of i-th elements (including 0) in it's solution else if (j >= weights[i]) { if (elementMatrix[i][j - weights[i]].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(true); }}Copy the code5. The traditional backpack problem
Using the two previous variants, let’s now look at the traditional knapsack problem and see how it differs from the simplified version:
Given a set of items, each with a weight w1, w2... and a value v1, v2... determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit k and the total value is as large as possible.
Copy the codeIn the simplified version, each solution is equally good. However, now we have a standard for finding the best solution (that is, the maximum possible). Remember, this time we have an unlimited number of projects per project, so projects can appear multiple times in the solution.
In the implementation, we’ll use the old class Element with a private field value added to store the maximum possible value for the stator problem:
public class Element {
private boolean exists;
private boolean includes;
private int value;
// appropriate constructors, getters and setters
}
Copy the codeThe implementation is very similar, the only difference being that now we must choose the best solution based on the resulting value:
public static void main(String[] args) {
// Same code as before with the addition of the values[] array
System.out.println("Insert values: ");
int[] values = new int[n + 1];
for (int i=1; i <= n; i++) {
values[i] = scanner.nextInt();
}
Element[][] elementMatrix = new Element[n + 1][k + 1];
// A matrix that indicates how many newest objects are used
// in the optimal solution.
// Example: contains[5][10] indicates how many objects with
// the weight of W[5] are contained in the optimal solution
// for a knapsack of capacity K=10
int[][] contains = new int[n + 1][k + 1];
elementMatrix[0][0] = new Element(0);
for (int i = 1; i <= n; i++) {
elementMatrix[i][0] = new Element(0);
contains[i][0] = 0;
}
for (int i = 1; i <= k; i++) {
elementMatrix[0][i] = new Element(0);
contains[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
elementMatrix[i][j] = new Element(elementMatrix[i - 1][j].getValue());
contains[i][j] = 0;
elementMatrix[i][j].setIncludes(false);
elementMatrix[i][j].setValue(M[i - 1][j].getValue());
if (j >= weights[i]) {
if ((elementMatrix[i][j - weights[i]].getValue() > 0 || j == weights[i])) {
if (elementMatrix[i][j - weights[i]].getValue() + values[i] > M[i][j].getValue()) {
elementMatrix[i][j].setIncludes(true);
elementMatrix[i][j].setValue(M[i][j - weights[i]].getValue() + values[i]);
contains[i][j] = contains[i][j - weights[i]] + 1;
}
}
}
System.out.print(elementMatrix[i][j].getValue() + "/" + contains[i][j] + "");
}
System.out.println();
}
System.out.println("Value: " + elementMatrix[n][k].getValue());
}
Copy the codeOutput:
Insert knapsack capacity: 12 Insert number of items: 5 Insert weights: 9 7 4 10 3 Insert values: 1, 2, 3, 4, 5 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 1/1 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 2/1 0/0 1/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 3/1 0/0 0/0 2/0 6/2 1/0 0/0 5/1 9/3 0/0 0/0 0/0 0/0 0/0 3/0 6/0 1/0 4/1 5/0 9/0 0/0 0/0 0/0 5/1 3/0 0/0 10/2 8/1 6/0 15/3 13/2 11/1 20/4 Value: 20Copy the code6. Levenshtein Distance
Another great example of dynamic programming is Edit Distance or Levenshtein Distance.
Levenshtein Distance is two strings A,B, which we need to convert from A to B using atomic operations:
- String deletion
- String insertion
- Character substitution (technically, it is more than one operation, but for simplicity we call it atomic operation)
This problem is handled by methodically solving the problem of substrings of the starting string, gradually increasing the size of the substrings until they are equal to the starting string.
The recursion we use for this problem is as follows:
a == b
C (a, b)
a = = b
C (a, b)
Implementation:
public class editDistance {
public static void main(String[] args) {
String s1, s2;
Scanner scanner = new Scanner(System.in);
System.out.println("Insert first string:");
s1 = scanner.next();
System.out.println("Insert second string:");
s2 = scanner.next();
int n, m;
n = s1.length();
m = s2.length();
// Matrix of substring edit distances
// example: distance[a][b] is the edit distance
// of the first a letters of s1 and b letters of s2
int[][] distance = new int[n + 1][m + 1];
// Matrix initialization:
// If we want to turn any string into an empty string
// the fastest way no doubt is to just delete
// every letter individually.
// The same principle applies if we have to turn an empty string
// into a non empty string, we just add appropriate letters
// until the strings are equal.
for (int i = 0; i <= n; i++) {
distance[i][0] = i;
}
for (int j = 0; j <= n; j++) {
distance[0][j] = j;
}
// Variables for storing potential values of current edit distance
int e1, e2, e3, min;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
e1 = distance[i - 1][j] + 1;
e2 = distance[i][j - 1] + 1;
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
e3 = distance[i - 1][j - 1];
} else {
e3 = distance[i - 1][j - 1] + 1;
}
min = Math.min(e1, e2);
min = Math.min(min, e3);
distance[i][j] = min;
}
}
System.out.println("Edit distance of s1 and s2 is: "+ distance[n][m]); }}Copy the codeOutput:
Insert first string:
man
Insert second string:
machine
Edit distance of s1 and s2 is: 3
Copy the codeIf you want to learn more about Levenshtein Distance solutions, we implemented Levenshtein Distance and Text Similarity in Python in another article, using this logic, We can boil down many string comparison algorithms to simple recursive relationships that use the basic formula of Levenshtein Distance
7. Longest Common SubSequence (LCS)
The problem is described as follows:
Given two sequences, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
Copy the codeGiven two sequences, find the length of the oldest sequence that exists in both sequences. Subsequences are sequences that occur in the same relative order, but are not necessarily continuous.
To clarify:
If we have two strings s1=”MICE” and s2=”MINCE”, the longest common subsequence is MI or CE. However, the longest common subsequence will be “MICE”, because the elements of the resulting subsequence need not be in a continuous order.
Recursive relations and general logic:
Levenshtein distance
LCS
In LCS, we don’t have the cost of character insertion and character deletion, which means we only count the cost of character replacement (diagonal movement), which is 1 if the two current string characters A [I] and B [j] are the same.
The final cost of LCS is the length of the oldest sequence of 2 strings, which is exactly what we need.
Using this logic, we can boil down a lot of string comparison algorithms to simple recurrence relations which utilize the base formula of the Levenshtein distance
Using this logic, we can reduce many string comparison algorithms to simple recursive relationships that use the basic formula of Levenshtein Distance.
Implementation:
public class LCS {
public static void main(String[] args) {
String s1 = new String("Hillfinger");
String s2 = new String("Hilfiger");
int n = s1.length();
int m = s2.length();
int[][] solutionMatrix = new int[n+1][m+1];
for (int i = 0; i < n; i++) {
solutionMatrix[i][0] = 0;
}
for (int i = 0; i < m; i++) {
solutionMatrix[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int max1, max2, max3;
max1 = solutionMatrix[i - 1][j];
max2 = solutionMatrix[i][j - 1];
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
max3 = solutionMatrix[i - 1][j - 1] + 1;
} else {
max3 = solutionMatrix[i - 1][j - 1];
}
int tmp = Math.max(max1, max2);
solutionMatrix[i][j] = Math.max(tmp, max3);
}
}
System.out.println("Length of longest continuous subsequence: "+ solutionMatrix[n][m]); }}Copy the codeOutput:
Length of longest continuous subsequence: 8
Copy the code8. Other issues using dynamic programming
Dynamic programming can solve many problems, some of which are listed below:
- Partition problem: Given a set of integers, find out if it can be divided into two subsets with equal sums
- Subsets and problems: Given an array of positive integers and its elements and a total value, is there a subset of the array whose elements add up to the total value?
- Coin variation problem: Find the total number of different ways to obtain the desired variation given the unlimited supply of coins of a given denomination
- All possible solutions to a linear equation with k variables: Given a linear equation with K variables, calculate the total number of possible solutions
- Find the probability that a drunk will not fall off a cliff: Given a linear space representing the distance to the cliff, calculate the probability of his survival by giving you the distance from the start of the cliff and his tendency to move towards cliff P and away from cliff 1-p
9. Conclusion
Dynamic programming is a tool, can save a lot of computation time, in return for a bigger space complexity, which to a large extent depends on the type of system you’re dealing with, if CPU time is precious, you choose to use memory solutions, on the other hand, if your memory is limited, the choice is more time consuming solution.
Original text: stackabuse.com/dynamic-pro…
Vladimir Batoć Anin
Translator: lee,
