Dynamic programming (DP) is one of the most basic and, at the same time, challenging programming paradigms. Some of the best algorithms that I know, such as the Levenshtein distance and DTW are implemented using this paradigm. It consists of simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner and then using the sub-problems’ precomputed solutions to solve the complicated one.
The key advantage of using DP is that it is fast. There are two key attributes that a problem must have in order for DP to be applicable: optimal substructure and overlapping sub-problems. In this post, I’ll rely on a set of representative DP problems to perform the two basic solution strategies: memoization and tabulation. These problems are presented and explained by Alvin Zablan, in this excellent video that he prepared for freeCodeCamp.org. I have written my own solutions to the problems in Java.
Strategies
The first indication that we are dealing with a DP problem is noticing overlapping sub-problems. Then, one has to decide what the trivially smallest input is. Depending on the implementation strategy to use, memoization (recursive) or tabulation (iterative), there are recipes that one can follow to address DP problems. For the memoization strategy, the most challenging step is to visualize the problem as a tree. When using the tabulation, finding the proper way to iterate through the table is usually the most challenging task.
Memoization
- Make it work
- visualize the problem as a tree (hard)
- implement the tree using recursion
- test it
- Make it efficient
- add a memo object
- add a base case to return memo values
- store return values into the memo
Tabulation
- Visualize the problem as a table
- Size the size of the table based on the inputs
- Initialize the table with default values
- Seed the trivial answer into the table
- Iterate through the table (hard)
- Fill further positions based on the current position
List of Problems
- Fibonacci (“What is the best way to do it?” → Optimization problem)
- Grid traveler (“How will you do it?” → Combinatorics problem)
- Can sum (“Can you do it?” → Decision problem)
- How sum (“How will you do it?” → Combinatorics problem)
- Best sum (“What is the best way to do it?” → Optimization problem)
- Can construct (“Can you do it?” → Decision problem)
- Count construct (“How will you do it?” → Combinatorics problem)
- All construct (“In how many ways can you do it?” → Combinatorics problem)
Fibonacci
Description: Write a function that returns the n-th number of the fibonacci sequence. To generate the next number of the sequence, we sum the previous two. For example, these are the first 10 fibonacci numbers:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| fib(n) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
Example:
Input: fib(8)
Output: 21Memoization Solution
1
2
3
4
5
6
7
static int fib(int n, Map<Integer, Integer> memo) {
if (memo.containsKey(n)) return memo.get(n);
if (n <= 2) return 1;
int value = fib(n - 1, memo) + fib(n - 2, memo);
memo.put(n, value);
return memo.get(n);
}
Tabulation Solution
1
2
3
4
5
6
7
8
9
static int fib(int n) {
List<Integer> l = new ArrayList(Collections.nCopies(n + 2, 0));
l.set(1, 1);
for (int i = 0; i < n; i++) {
l.set(i + 1, l.get(i) + l.get(i + 1));
l.set(i + 2, l.get(i) + l.get(i + 2));
}
return l.get(n);
}
Grid Traveler
Description: You are a traveler on a 2D grid. You begin in the top-left corner and your goal is to travel to the bottom-right corner. You may only move down or right. In how many ways can you travel to the goal on a grid with dimensions n*m.
Example:
Input: gridTraveler(2, 3)
Output: 3Memoization Solution
1
2
3
4
5
6
7
8
static long gridTraveler(int m, int n, Map<String, Long> memo) {
String key = m + "," + n;
if (memo.containsKey(key)) return memo.get(key);
if (n == 1 && m == 1) return 1;
if (n == 0 || m == 0) return 0;
memo.put(key, function(n - 1, m, memo) + function(n, m - 1, memo));
return memo.get(key);
}
Tabulation Solution
1
2
3
4
5
6
7
8
9
10
11
12
static long gridTraveler(int m, int n) {
long[][] table = new long[m + 1][n + 1];
table[1][1] = 1;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
long current = table[i][j];
if (i + 1 <= m) table[i + 1][j] += current;
if (j + 1 <= n) table[i][j + 1] += current;
}
}
return table[m][n];
}
Can Sum
Description: Write a function that return a boolean indicating whether it is possible to generate a targetSum value by adding number from a given array. Elements of the array are positive integers and can be used as many time as needed.
Example:
Input: canSum(7, new int[]{5, 3, 4, 7})
Output: trueMemoization Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static boolean canSum(int targetSum, int[] numbers, Map<Integer, Boolean> memo) {
if (memo.containsKey(targetSum)) return memo.get(targetSum);
if (targetSum == 0) return true;
if (targetSum < 0) return false;
for (int number : numbers) {
int remainder = targetSum - number;
if (canSum(remainder, numbers, memo)){
memo.put(targetSum, true);
return true;
}
}
memo.put(targetSum, false);
return false;
}
Tabulation Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static boolean canSum(int targetSum, int[] numbers) {
boolean[] table = new boolean[targetSum + 1];
table[0] = true;
for (int i = 0; i < table.length; i++) {
if (table[i]) {
for (Integer num : numbers) {
if (i + num < table.length) {
table[i + num] = true;
}
}
}
}
return table[targetSum];
}
How Sum
Description: Write a function that return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the targetSum, then return null.
Example:
Input: howSum(7, new int[]{5, 3, 4, 7})
Output: [3, 4] // or [7]Memoization Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static List<Integer> howSum(int targetSum, int[] numbers, Map<Integer, List<Integer>> memo) {
if (memo.containsKey(targetSum)) return memo.get(targetSum);
if (targetSum == 0) return new ArrayList<>();
if (targetSum < 0) return null;
for (int number : numbers) {
int remainder = targetSum - number;
List<Integer> result = howSum(remainder, numbers, memo);
if (result != null) {
result.add(number);
memo.put(targetSum, result);
return memo.get(targetSum);
}
}
memo.put(targetSum, null);
return null;
}
Tabulation Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static List<Integer> howSum(int targetSum, int[] numbers) {
// Initialize a list of null elements except the first element
List<List<Integer>> table = new ArrayList<>(targetSum + 1);
table.add(0, new ArrayList<>());
for (int i = 1; i < targetSum; i++) {
table.add(i, null);
}
// Algorithm
for (int i = 0; i < targetSum; i++) {
if (table.get(i) != null) {
for (int j = 0; j < numbers.length; j++) {
Integer num = numbers[j];
List<Integer> l = new ArrayList<>(table.get(i));
l.add(num);
table.add(i + num, l);
}
}
}
return table.get(targetSum);
}
Best Sum
Description: Write a function that returns an array containing the shortest combination of numbers that add up to exactly the targetSum. If there is a tie fo the shortest combination, you may return any one of the shortest.
Example:
Input: bestSum(7, new int[]{5, 3, 4, 7})
Output: [7]Memoization Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static List<Integer> bestSum(int targetSum, int[] numbers, Map<Integer, List<Integer>> memo) {
if (memo.containsKey(targetSum)) return memo.get(targetSum);
if (targetSum == 0) return new ArrayList<>();
if (targetSum < 0) return null;
List<Integer> shortestCombination = null;
for (int num : numbers) {
int remainder = targetSum - num;
List<Integer> remainderCombination = bestSum(remainder, numbers, memo);
if (remainderCombination != null) {
List<Integer> combination = new ArrayList<>();
combination.addAll(remainderCombination);
combination.add(num);
if (shortestCombination == null ||
combination.size() < shortestCombination.size()) {
shortestCombination = combination;
}
}
}
memo.put(targetSum, shortestCombination);
return shortestCombination;
}
Tabulation Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static List<Integer> bestSum(int targetSum, int[] numbers) {
// Initialize a list of null elements except the first element
List<List<Integer>> table = new ArrayList<>(targetSum + 1);
table.add(0, new ArrayList<>());
for (int i = 1; i <= targetSum; i++) {
table.add(i, null);
}
// Algorithm
for (int i = 0; i < targetSum; i++) {
if (table.get(i) != null) {
for (int j = 0; j < numbers.length; j++) {
int num = numbers[j];
List<Integer> combination = new ArrayList<>(table.get(i));
combination.add(num);
if (i + num <= targetSum) {
if (table.get(i + num) == null) {
table.set(i + num, combination);
} else if (combination.size() < table.get(i + num).size()) {
table.set(i + num, combination);
}
}
}
}
}
return table.get(targetSum);
}
Can Construct
Description: Write a function that returns a boolean indication whether the target string can be constructed by concatenating elements of the wordBank array of strings. Elements in wordBank can be reused as many times as needed.
Example:
Input: canConstruct("abcdef", new String[]{"ab", "abc", "cd", "def", "abcd"})
Output: trueMemoization Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static boolean canConstruct(String target, String[] wordBank, Map<String, Boolean> memo) {
if (memo.containsKey(target)) return memo.get(target);
if (target.equals("")) return true;
for (String word : wordBank) {
if (target.startsWith(word)) {
String reducedTarget = target.substring(word.length());
if (canConstruct(reducedTarget, wordBank, memo)) {
memo.put(reducedTarget, true);
return true;
}
}
}
memo.put(target, false);
return false;
}
Tabulation Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static boolean canConstruct(String target, String[] wordBank) {
// Initialize a list of false boolean elements except the first element
List<Boolean> table = new ArrayList<>();
for (int i = 0; i < target.length() + 1; i++) {
table.add(i, false);
}
table.set(0, true);
// Algorithm
for (int i = 0; i < table.size(); i++) {
if (table.get(i)) {
for (String word : wordBank) {
// if the word matches the characters starting at position i
if (target.startsWith(word, i)) {
table.set(i + word.length(), true);
}
}
}
}
return table.get(target.length());
}
Count Construct
Description: Write a function that returns the number of ways that the target can be constructed by concatenating elements of the wordBank array. Elements in wordBank can be reused as many times as needed.
Example:
Input: countConstruct("purple", new String[]{"purp", "p", "ur", "le", "purpl"})
Output: 2Memoization Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int countConstruct(String target, String[] wordBank, Map<String, Integer> memo) {
if (memo.containsKey(target)) return memo.get(target);
if (target.equals("")) return 1;
int totalCount = 0;
for (String word : wordBank) {
if (target.startsWith(word)) {
String reducedTarget = target.substring(word.length());
int numWaysForRest = countConstruct(reducedTarget, wordBank, memo);
totalCount += numWaysForRest;
}
}
memo.put(target, totalCount);
return totalCount;
}
Tabulation Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int countConstruct(String target, String[] wordBank) {
// Initialize a list of integer elements with zero except the first element
List<Integer> table = new ArrayList<>();
for (int i = 0; i < target.length() + 1; i++) {
table.add(i, 0);
}
table.set(0, 1);
// Algorithm
for (int i = 0; i < table.size(); i++) {
for (String word : wordBank) {
if (target.startsWith(word, i)) {
int valueAtCurrentPosition = i + word.length();
table.set(valueAtCurrentPosition, table.get(i) + table.get(valueAtCurrentPosition));
}
}
}
return table.get(target.length());
}
All Construct
Description: Write a function that returns a 2D array containing all the ways that the target can be constructed by concatenating elements of the wordBank array. Each element of the 2D array should represent one combination that constructs the target. Elements in wordBank can be reused as many times as needed.
Example:
Input: allConstruct("abcdef", new String[]{"ab", "abc", "cd", "def", "abcd", "ef", "c"})
Output: {["ab", "cd", "ef"],
["ab", "c", "def"],
["abc", "def"],
["abcd", "ef"]
}Memoization Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static List<List<String>> allConstruct(String target, String[] wordBank, Map<String, List<List<String>>> memo) {
if(memo.containsKey(target)) return memo.get(target);
if (target.equals("")) {
List<List<String>> tmp = new ArrayList<>();
List<String> list = new ArrayList<>();
tmp.add(list);
return tmp; // a list with one element [[]]
}
List<List<String>> result = new ArrayList<>();
for (String word : wordBank) {
if (target.startsWith(word)) {
String suffix = target.substring(word.length());
List<List<String>> suffixWays = allConstruct(suffix, wordBank, memo);
List<List<String>> targetWays = new ArrayList<>();
for (List<String> suffixWay : suffixWays) {
List<String> tmp = new ArrayList<>(suffixWay);
tmp.add(0, word);
targetWays.add(tmp);
}
result.addAll(targetWays);
}
}
memo.put(target, result);
return result;
}
Tabulation Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static List<List<String>> allConstruct(String target, String[] wordBank) {
// Initialize a list of lists representing each combination of words from wordBank
List<List<List<String>>> table = new ArrayList<>();
for (int i = 0; i < target.length() + 1; i++) {
table.add(i, new ArrayList<>());
}
table.get(0).add(0, new ArrayList<>());
// Algorithm
for (int i = 0; i < table.size(); i++) {
for (String word : wordBank) {
if (target.startsWith(word, i)) {
List<List<String>> combinations = new ArrayList<>();
for (List<String> combination : table.get(i)) {
combinations.add(new ArrayList<>(combination));
}
for (List<String> combination : combinations) {
combination.add(word);
}
for (List<String> combination : combinations) {
table.get(i + word.length()).add(combination);
}
}
}
}
return table.get(target.length());
}
