Author: Jacob Park
A dynamic programming algorithm is an algorithm that solves problems by combining the solutions to overlapping subproblems without repetition.
The input is $x_{1}, x_{2}, ..., x_{n}$ and a subproblem is $x_{1}, x_{2}, ..., x_{i}$.
$$[x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}], x_{7}, x_{8}, x_{9}, x_{10}$$
The number of subproblems is $O(n)$.
The input is $x_{1}, x_{2}, ..., x_{n}$ and $y_{1}, y_{2}, ..., y_{m}$. A subproblem is $x_{1}, x_{2}, ..., x_{i}$ and $y_{1}, y_{2}, ..., y_{j}$.
$$[x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}], x_{7}, x_{8}, x_{9}, x_{10}$$ $$[y_{1}, y_{2}, y_{3}, x_{4}, y_{5}], y_{6}, y_{7}, y_{8}$$
The number of subproblems is $O(nm)$.
The input is $x_{1}, x_{2}, ..., x_{n}$ and a subproblem is $x_{i}, x_{i + 1}, ..., x_{j}$.
$$x_{1}, x_{2}, [x_{3}, x_{4}, x_{5}, x_{6}], x_{7}, x_{8}, x_{9}, x_{10}$$
The number of subproblems is $O(n^2)$.
The input is a rooted tree. A subproblem is a rooted subtree.
package dynamic_programming.example.fibonacci_number;
import java.util.*;
public class FibonacciNumber {
/*
* Recursive Definition:
* F(0) = 0
* F(1) = 1
* F(x) = F(x - 1) + F(x - 2)
*/
public static int fibonacci(int n) {
final Map<Integer, Integer> solutions = new HashMap<>();
solutions.put(0, 0);
solutions.put(1, 1);
for (int currentN = 2; currentN <= n; currentN++) {
final int previousSolution1 = solutions.get(currentN - 1);
final int previousSolution2 = solutions.get(currentN - 2);
final int currentSolution = previousSolution1 + previousSolution2;
solutions.put(currentN, currentSolution);
}
return solutions.get(n);
}
}
package dynamic_programming.example.fibonacci_number;
System.out.println(String.format(
"10th Fibonacci Number: %d", FibonacciNumber.fibonacci(10)));
package dynamic_programming.example.change_making;
import java.util.*;
public class ChangeMaking {
/*
* Recursive Definition:
* MNOC(0) = 0
* MNOC(1) = MNOC(5) = MNOC(10) = MNOC(25) = 1
* MNOC(x) = 1 + Minimum(MNOC(x - 1), MNOC(x - 5), MNOC(x - 10), MNOC(x - 25).
*/
public static int minimumNumberOfCoins(int n) {
final Map<Integer, Integer> solutions = new HashMap<>();
solutions.put(0, 0);
solutions.put(1, 1);
solutions.put(5, 1);
solutions.put(10, 1);
solutions.put(25, 1);
for (int currentN = 2; currentN <= n; currentN++) {
final List<Integer> validSolutions = new LinkedList<>();
if (currentN - 1 >= 0) {
validSolutions.add(solutions.get(currentN - 1));
}
if (currentN - 5 >= 0) {
validSolutions.add(solutions.get(currentN - 5));
}
if (currentN - 10 >= 0) {
validSolutions.add(solutions.get(currentN - 10));
}
if (currentN - 25 >= 0) {
validSolutions.add(solutions.get(currentN - 25));
}
final int currentSolution = 1 + Collections.min(validSolutions);
solutions.put(currentN, currentSolution);
}
return solutions.get(n);
}
}
package dynamic_programming.example.change_making;
System.out.println(String.format(
"Minimum Number of Coins: %d", ChangeMaking.minimumNumberOfCoins(49)));
package dynamic_programming.example.maximum_size_square_sub_matrix;
import java.util.*;
public class MaximumSizeSquareSubMatrix {
private static class Position {
private final int indexX;
private final int indexY;
public Position(int indexX, int indexY) {
this.indexX = indexX;
this.indexY = indexY;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
final Position position = (Position) o;
return indexX == position.indexX && indexY == position.indexY;
}
@Override
public int hashCode() {
return Objects.hash(indexX, indexY);
}
}
/*
* Recursive Definition:
* MSSSM(x, 0) = M[x][0] == 1 ? 1 : 0
* MSSSM(0, y) = M[0][y] == 1 ? 1 : 0
* MSSSM(x, y) = M[x][y] == 1 ? 1 +
* Minimum(MSSSM(x - 1, y), MSSSM(x, y - 1), MSSSM(x - 1, y - 1)) : 0
*/
public static int maximumSizeSquareSubMatrix(int[][] matrix) {
final Map<Position, Integer> solutions = new HashMap<>();
int currentMaxLength = 0;
for (int indexX = 0; indexX < matrix.length; indexX++) {
final Position currentPosition = new Position(indexX, 0);
final int currentSolution = matrix[indexX][0] == 1 ? 1 : 0;
solutions.put(currentPosition, currentSolution);
if (currentMaxLength < currentSolution) {
currentMaxLength = currentSolution;
}
}
for (int indexY = 0; indexY < matrix[0].length; indexY++) {
final Position currentPosition = new Position(0, indexY);
final int currentSolution = matrix[0][indexY] == 1 ? 1 : 0;
solutions.put(currentPosition, currentSolution);
if (currentMaxLength < currentSolution) {
currentMaxLength = currentSolution;
}
}
for (int indexX = 1; indexX < matrix.length; indexX++) {
for (int indexY = 1; indexY < matrix[0].length; indexY++) {
final Position currentPosition = new Position(indexX, indexY);
final int leftPosition =
solutions.get(new Position(indexX - 1, indexY));
final int topPosition =
solutions.get(new Position(indexX, indexY - 1));
final int topLeftPosition =
solutions.get(new Position(indexX - 1, indexY - 1));
final int minimumLength = Collections.min(
Arrays.asList(leftPosition, topPosition, topLeftPosition));
final int currentSolution =
matrix[indexX][indexY] == 1 ? 1 + minimumLength : 0;
solutions.put(currentPosition, currentSolution);
if (currentMaxLength < currentSolution) {
currentMaxLength = currentSolution;
}
}
}
return currentMaxLength * currentMaxLength;
}
}
package dynamic_programming.example.maximum_size_square_sub_matrix;
final int[][] matrix = new int[][] {
new int[] {0, 1, 0, 0},
new int[] {1, 1, 1, 1},
new int[] {0, 1, 1, 0}
};
System.out.println(String.format(
"Maximum Size Square Sub-Matrix: %d", MaximumSizeSquareSubMatrix.maximumSizeSquareSubMatrix(matrix)));
package dynamic_programming.example.zero_one_knapsack;
import java.util.*;
public class ZeroOneKnapsack {
public static class Item {
private final int value;
private final int weight;
public Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
public int getValue() {
return value;
}
public int getWeight() {
return weight;
}
}
private static class ItemWeightPair {
private final int item;
private final int weight;
public ItemWeightPair(int item, int weight) {
this.item = item;
this.weight = weight;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
final ItemWeightPair that = (ItemWeightPair) o;
return item == that.item && weight == that.weight;
}
@Override
public int hashCode() {
return Objects.hash(item, weight);
}
}
/*
* Recursive Definition:
* MVK(-1, w) = 0
* MVK(i, w) = weight(i) <=
* w ? Maximum(MVK(i - 1, w), value(i) + MVK(i - 1, w - weight(i))) : MVK(i - 1, w)
*/
public static int maximumValueKnapsack(int weight, Item[] items) {
final Map<ItemWeightPair, Integer> solutions = new HashMap<>();
for (int currentWeight = 0; currentWeight <= weight; currentWeight++) {
solutions.put(new ItemWeightPair(-1, currentWeight), 0);
}
// The optimal structure requires choosing an optimal combination,
// so consider whether the inclusion or the exclusion of
// the item satisfies the constraint, for all items, for all constraints.
for (int currentItem = 0; currentItem < items.length; currentItem++) {
for (int currentWeight = 0; currentWeight <= weight; currentWeight++) {
final int currentItemValue = items[currentItem].getValue();
final int currentItemWeight = items[currentItem].getWeight();
// If you can't include it, ignore the current solution.
// Else, make an optimal choice between including it and not including it.
if (currentItemWeight > currentWeight) {
final int previousSolution =
solutions.get(new ItemWeightPair(currentItem - 1, currentWeight));
solutions.put(
new ItemWeightPair(currentItem, currentWeight),
previousSolution);
} else {
final int previousSolutionWithoutItem =
solutions.get(new ItemWeightPair(currentItem - 1, currentWeight));
final int previousSolutionWithItem =
currentItemValue + solutions.get(new ItemWeightPair(currentItem - 1, currentWeight - currentItemWeight));
final int currentSolution =
Math.max(previousSolutionWithoutItem, previousSolutionWithItem);
solutions.put(
new ItemWeightPair(currentItem, currentWeight),
currentSolution);
}
}
}
return solutions.get(new ItemWeightPair(items.length - 1, weight));
}
}
package dynamic_programming.example.zero_one_knapsack;
final ZeroOneKnapsack.Item[] items = new ZeroOneKnapsack.Item[] {
new ZeroOneKnapsack.Item(6, 2),
new ZeroOneKnapsack.Item(10, 2),
new ZeroOneKnapsack.Item(12, 3)
};
System.out.println(String.format(
"Max Value of Knapsack: %d", ZeroOneKnapsack.maximumValueKnapsack(5, items)));
package dynamic_programming.example.subset_sum;
import java.util.*;
public class SubsetSum {
private static class IndexSumPair {
private final int index;
private final int sum;
public IndexSumPair(int index, int sum) {
this.index = index;
this.sum = sum;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
final IndexSumPair that = (IndexSumPair) o;
return index == that.index && sum == that.sum;
}
@Override
public int hashCode() {
return Objects.hash(index, sum);
}
}
/*
* Recursive Definition:
* ISS(-1, s) = false
* ISS(-1, 0) = true
* ISS(i, s) = value(i) <= s ? ISS(i - 1, s) || ISS(i - 1, s - value(i)) : ISS(i - 1, s)
*/
public static boolean isSubsetSum(int[] set, int sum) {
final Map<IndexSumPair, Boolean> solutions = new HashMap<>();
for (int currentSum = 0; currentSum <= sum; currentSum++) {
solutions.put(new IndexSumPair(-1, currentSum), false);
}
solutions.put(new IndexSumPair(-1, 0), true);
// The optimal structure requires choosing an optimal combination,
// so consider whether the inclusion or the exclusion of
// the item satisfies the constraint, for all items, for all constraints.
for (int currentItemIndex = 0; currentItemIndex < set.length; currentItemIndex++) {
for (int currentSum = 0; currentSum <= sum; currentSum++) {
final int currentItem = set[currentItemIndex];
// If you can't include it, ignore the current solution.
// Else, make an optimal choice between including it and not including it.
if (currentItem > currentSum) {
final boolean previousSolution =
solutions.get(new IndexSumPair(currentItemIndex - 1, currentSum));
solutions.put(
new IndexSumPair(currentItemIndex, currentSum),
previousSolution);
} else {
final boolean previousSolutionWithoutItem =
solutions.get(new IndexSumPair(currentItemIndex - 1, currentSum));
final boolean previousSolutionWithItem =
solutions.get(new IndexSumPair(currentItemIndex - 1, currentSum - currentItem));
final boolean currentSolution =
previousSolutionWithoutItem || previousSolutionWithItem;
solutions.put(
new IndexSumPair(currentItemIndex, currentSum),
currentSolution);
}
}
}
return solutions.get(new IndexSumPair(set.length - 1, sum));
}
}
package dynamic_programming.example.subset_sum;
final int[] set = new int[] {3, 34, 4, 12, 5, 2};
System.out.println(String.format(
"Is Subset Sum: %b", SubsetSum.isSubsetSum(set, 9)));
package dynamic_programming.example.longest_common_subsequence;
import java.util.*;
public class LongestCommonSubsequence {
private static class ABPair {
private final int a;
private final int b;
public ABPair(int a, int b) {
this.a = a;
this.b = b;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
final ABPair abPair = (ABPair) o;
return a == abPair.a && b == abPair.b;
}
@Override
public int hashCode() {
return Objects.hash(a, b);
}
}
/*
* Recursive Definition:
* LCS(a, 0) = 0
* LCS(0, b) = 0
* LCS(a, b) = A[a - 1] == B[b - 1] ? 1 + LCS(a - 1, b - 1) : Maximum(LCS(a, b - 1), LCS(a - 1, b))
*/
public static int longestCommonSubsequence(String a, String b) {
final Map<ABPair, Integer> solutions = new HashMap<>();
for (int aLength = 0; aLength <= a.length(); aLength++) {
solutions.put(new ABPair(aLength, 0), 0);
}
for (int bLength = 0; bLength <= b.length(); bLength++) {
solutions.put(new ABPair(0, bLength), 0);
}
for (int aLength = 1; aLength <= a.length(); aLength++) {
for (int bLength = 1; bLength <= b.length(); bLength++) {
if (a.charAt(aLength - 1) == b.charAt(bLength - 1)) {
final int previousSolutionWithoutAB =
solutions.get(new ABPair(aLength - 1, bLength - 1));
final int currentSolution =
1 + previousSolutionWithoutAB;
solutions.put(new ABPair(aLength, bLength), currentSolution);
} else {
final int previousSolutionWithoutA =
solutions.get(new ABPair(aLength, bLength - 1));
final int previousSolutionWithoutB =
solutions.get(new ABPair(aLength - 1, bLength));
final int currentSolution =
Math.max(previousSolutionWithoutA, previousSolutionWithoutB);
solutions.put(new ABPair(aLength, bLength), currentSolution);
}
}
}
return solutions.get(new ABPair(a.length(), b.length()));
}
}
package dynamic_programming.example.longest_common_subsequence;
final String a = "ABCD";
final String b = "EACB";
System.out.println(String.format(
"Length of Longest Common Subsequence: %d", LongestCommonSubsequence.longestCommonSubsequence(a, b)));
package dynamic_programming.example.edit_distance;
import java.util.*;
public class EditDistance {
private static class ABPair {
private final int a;
private final int b;
public ABPair(int a, int b) {
this.a = a;
this.b = b;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
final ABPair abPair = (ABPair) o;
return a == abPair.a && b == abPair.b;
}
@Override
public int hashCode() {
return Objects.hash(a, b);
}
}
/*
* Recursive Definition:
* MED(a, 0) = a
* MED(0, b) = b
* MED(a, b) = A[a - 1] == B[b - 1] ? MED(a - 1, b - 1) : Minimum(MED(a, b - 1), MED(a - 1, b), MED(a - 1, b - 1))
*/
public static int minimumEditDistance(String a, String b) {
final Map<ABPair, Integer> solutions = new HashMap<>();
for (int aLength = 0; aLength <= a.length(); aLength++) {
for (int bLength = 0; bLength <= b.length(); bLength++) {
if (aLength == 0) {
solutions.put(new ABPair(aLength, bLength), bLength);
} else if (bLength == 0) {
solutions.put(new ABPair(aLength, bLength), aLength);
} else if (a.charAt(aLength - 1) == b.charAt(bLength - 1)) {
final int previousSolution =
solutions.get(new ABPair(aLength - 1, bLength - 1));
solutions.put(new ABPair(aLength, bLength), previousSolution);
} else {
final int previousSolutionInsert =
solutions.get(new ABPair(aLength, bLength - 1));
final int previousSolutionDelete =
solutions.get(new ABPair(aLength - 1, bLength));
final int previousSolutionReplace =
solutions.get(new ABPair(aLength - 1, bLength - 1));
final int currentSolution = 1 + Collections.min(Arrays.asList(
previousSolutionInsert,
previousSolutionDelete,
previousSolutionReplace));
solutions.put(new ABPair(aLength, bLength), currentSolution);
}
}
}
return solutions.get(new ABPair(a.length(), b.length()));
}
}
package dynamic_programming.example.edit_distance;
final String a = "SUNDAY";
final String b = "SATURDAY";
System.out.println(String.format(
"Minimum Edit Distance: %d", EditDistance.minimumEditDistance(a, b)));
package dynamic_programming.example.longest_increasing_subsequence;
import java.util.*;
public class LongestIncreasingSubsequence {
/*
* Recursive Definition:
* LIS(e) = 1
* LIS(e) = S[s] < S[e] ? Maximum(1 + LIS(s), LIS(e))
*/
public static int longestIncreasingSubsequence(int[] S) {
final Map<Integer, Integer> solutions = new HashMap<>();
for (int endIndex = 0; endIndex < S.length; endIndex++) {
solutions.put(endIndex, 1);
}
for (int endIndex = 1; endIndex < S.length; endIndex++) {
for (int startIndex = 0; startIndex < endIndex; startIndex++) {
if (S[startIndex] < S[endIndex]) {
final int previousSolution = solutions.get(endIndex);
final int currentSolution = 1 + solutions.get(startIndex);
solutions.put(endIndex, Math.max(previousSolution, currentSolution));
}
}
}
int max = 0;
for (Integer currentLength : solutions.values()) {
if (currentLength > max) {
max = currentLength;
}
}
return max;
}
}
package dynamic_programming.example.longest_increasing_subsequence;
System.out.println(String.format(
"Longest Increasing Subsequence Length: %d", LongestIncreasingSubsequence.longestIncreasingSubsequence(new int[] {3, 10, 2, 1, 20})));