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

- visualize the problem as a tree (
- 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

# Problems

- Fibonacci (“What is the best way to do it?” -> Optimization problem)
- Grid traveler (“How will you do it?” -> Combinatoric problem)
- Can sum (“Can you do it?” -> Decision problem)
- How sum (“How will you do it?” -> Combinatoric 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?” -> Combinatoric problem)
- All construct (“In how many ways can you do it?” -> Combinatoric 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:**

### Memoization 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:**

### Memoization 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:**

### Memoization 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:**

### 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:**

### 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:**

### Memoization 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:**

### Memoization 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:**

### 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());
}