Introduction

Dynamic Programming(DP) is a problem-solving approach in computer science that optimizes solutions by storing the results of subproblems to avoid performing the same calculation repeatedly.

Here's a list of canonical problems used to study DP.

1. Fibonacci
2. Grid Traveler
3. Can Sum
4. How Sum
5. Best Sum
6. Can Construct
7. Count Construct
8. All Construct

We'll implement solutions with Brute Force, Top-Down Memoization, & Bottom-Up Tabulation to develop our understanding of DP.

Approach	Recursion	Cache/Table	Time	Space	Description
Brute Force (No DP)	❌	❌	O(2ⁿ)	O(n)	Tries all possibilities without storing results
Top-Down (Memoization)	✅	✅	O(n)	O(n) or more	Recursively solves subproblems, caching results
Bottom-Up (Tabulation)	❌	✅	O(n)	O(n)	Iteratively builds solution from base cases

1. Fibonacci

Write a function fib(n) that takes in a number as an argument.

The function should return the n-th number of the fibonacci sequence.

1// Brute force solution works but is slow due to
2// repetitive computations made.
3 
4const fib = (n) => {
5  if (n <= 2) return 1
6  return fib(n - 1) + fib(n - 2)
7}
8 
9console.log(fib(50)) // 12586269025
10 
11// time = O(2ⁿ)
12// space = O(n)

1// Saving results of computations in `memo` improves the performance.
2 
3// Memo starts empty dictionary but populates values
4// from the first branch of our recursive
5// calls(meaning that subsequent branches don't recompute
6// the same value but fetch it from the dict).
7 
8const fib = (n, memo = {}) => {
9  if (n in memo) return memo[n]
10  if (n <= 2) return 1
11  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
12  return memo[n]
13}
14 
15console.log(fib(50))
16 
17// time = O(n)
18// space = O(n)

1// In this case we don't utilize recursion but tabulation to store values.
2// We loop until we reach `n` at which point the `n` index contains our answer.
3 
4const fib = (n) => {
5  if (n <= 2) return 1
6  const dp = [0, 1, 1]
7  for (let i = 3; i <= n; i++) {
8    dp[i] = dp[i - 1] + dp[i - 2]
9  }
10  return dp[n]
11}
12 
13console.log(fib(50))
14 
15// time = O(n)
16// space = O(n)

2. Grid Traveler

Write a function gridTraveler(m, n) that returns the number of ways to travel from top left to bottom right corner of grid.

1// We start from the end and work back by subtracting from `m` & `n`.
2// When we reach our base case of being in the top left(m == 1 && n == 1) 
3// we increment the count of how many unique ways we can traverse the grid.
4 
5const gridTraveler = (m, n) => {
6  if (m === 1 && n === 1) return 1
7  if (m === 0 || n === 0) return 0
8  return gridTraveler(m - 1, n) + gridTraveler(m, n - 1)
9}
10 
11console.log(gridTraveler(18, 18)) // 2333606220
12 
13// time = O(2ᵐ⁺ⁿ)
14// space = O(m+n)

1// By storing each cell's number of unique paths to reach the
2// beginning we don't repeat computations and thus improve the performance of our algorithm a lot.
3 
4const gridTraveler = (m, n, memo = {}) => {
5  const key = m + ',' + n
6 
7  if (key in memo) return memo[key]
8 
9  if (m === 1 && n === 1) return 1
10  if (m === 0 || n === 0) return 0
11 
12  memo[key] = gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo)
13  return memo[key]
14}
15 
16console.log(gridTraveler(18, 18)) // 2333606220
17 
18// time = O(m * n)
19// space = O(m * n)

1// Using a 2d array we start each cell as 0 and then carry the values right 
2// & down(up) toward the bottom right. In each cell we sum the cell from which we just came and the cell in which we land.
3// Thus by the end we have our solution.
4 
5const gridTraveler = (m, n) => {
6  const dp = Array(m + 1)
7    .fill()
8    .map(() => Array(n + 1).fill(0))
9 
10  dp[1][1] = 1
11 
12  for (let i = 1; i <= m; i++) {
13    for (let j = 1; j <= n; j++) {
14      if (i + 1 <= m) dp[i + 1][j] += dp[i][j]
15      if (j + 1 <= n) dp[i][j + 1] += dp[i][j]
16    }
17  }
18  return dp[m][n]
19}
20 
21console.log(gridTraveler(18, 18))
22 
23// time = O(m × n)
24// space = O(m × n)

3. Can Sum

Write a function canSum(target, nums) that takes in a target sum and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the target using numbers from the array.

You may use an element of the array as many times as needed.

You may assume that all inputs are non negative.

1const canSum = (target, nums) => {
2  if (target === 0) return true
3  if (target < 0) return false
4  for (const n of nums) {
5    const remainder = target - n
6    if (canSum(remainder, nums) === true) {
7      return true
8    }
9  }
10  return false
11}
12console.log(canSum(7, [2, 3]))          // true
13console.log(canSum(8, [2, 3, 5]))       // true
14console.log(canSum(7, [5, 3, 4, 7]))    // true
15console.log(canSum(7, [5, 3, 4, 7]))    // true
16console.log(canSum(7, [2, 4]))          // false
17console.log(canSum(300, [7, 14]))       // false
18 
19// time = O(nᵐ)
20// space = O(m)

1const canSum = (target, nums, memo = {}) => {
2  if (target in memo) return memo[target]
3  if (target === 0) return true
4  if (target < 0) return false
5 
6  for (let n of nums) {
7    const remainder = target - n
8    if (canSum(remainder, nums, memo) === true) {
9      memo[target] = true
10      return true
11    }
12  }
13 
14  memo[target] = false
15  return false
16}
17 
18console.log(canSum(7, [2, 3]))        // true
19console.log(canSum(8, [2, 3, 5]))     // true
20console.log(canSum(7, [5, 3, 4, 7]))  // true
21console.log(canSum(7, [5, 3, 4, 7]))  // true
22console.log(canSum(7, [2, 4]))        // false
23console.log(canSum(300, [7, 14]))     // false
24 
25// time = O(n * m)
26// space = O(m)

1const canSum = (target, nums) => {
2  const dp = Array(target + 1).fill(false)
3  dp[0] = true
4 
5  for (let i = 0; i <= target; i++) {
6    if (dp[i]) {
7      for (let n of nums) {
8        if (i + n <= target) {
9          dp[i + n] = true
10        }
11      }
12    }
13  }
14 
15  return dp[target]
16}
17 
18console.log(canSum(7, [2, 3]))        // true
19console.log(canSum(8, [2, 3, 5]))     // true
20console.log(canSum(7, [5, 3, 4, 7]))  // true
21console.log(canSum(7, [5, 3, 4, 7]))  // true
22console.log(canSum(7, [2, 4]))        // false
23console.log(canSum(300, [7, 14]))     // false
24 
25// time = O(n * m) where n is the target & m the length of nums.
26// space = O(m) where m is the length of nums.

4. How Sum

Write a function howSum(target, nums) that takes in a target and an array of numbers as arguments.

The function should return an array containing any combination of elements that add up to exactly target. If there is no combination that adds up to the target, then return null.

If there are multiple combinations possible you may return any single one.

1const howSum = (target, nums) => {
2  if (target === 0) return []
3  if (target < 0) return null
4  for (const n of nums) {
5    const remainder = target - n
6    const result = howSum(remainder, nums)
7    if (result !== null) {
8      return [...result, n]
9    }
10  }
11  return null
12}
13 
14console.log(howSum(7, [2, 3]))        // [3, 2, 2]
15console.log(howSum(7, [5, 3, 4, 7]))  // [4, 3]
16console.log(howSum(7, [2, 4]))        // null
17console.log(howSum(8, [2, 3, 5]))     // [2, 2, 2, 2]
18console.log(howSum(300, [7, 14]))     // null
19 
20// time = O(nᵐ⁺ⁿ) where n is the length of the array & m is target
21// space = O(m) where m is target

1const howSum = (target, nums, memo = {}) => {
2  if (target in memo) return memo[target]
3  if (target === 0) return []
4  if (target < 0) return null
5  for (const n of nums) {
6    const remainder = target - n
7    const result = howSum(remainder, nums, memo)
8    if (result !== null) {
9      memo[target] = [...result, n]
10      return memo[target]
11    }
12  }
13  memo[target] = null
14  return null
15}
16 
17console.log(howSum(7, [2, 3]))        // [3, 2, 2]
18console.log(howSum(7, [5, 3, 4, 7]))  // [4, 3]
19console.log(howSum(7, [2, 4]))        // null
20console.log(howSum(8, [2, 3, 5]))     // [2, 2, 2, 2]
21console.log(howSum(300, [7, 14]))     // null
22 
23// time = O(m * n) where n is the length of the array & m is target
24// space = O(m) where m is target

1const howSum = (target, nums) => {
2  const dp = Array(target + 1).fill(null)
3  dp[0] = []
4 
5  for (let i = 0; i < target; i++) {
6    if (dp[i] !== null) {
7      for (const n of nums) {
8        dp[i + n] = [...dp[i], n]
9      }
10    }
11  }
12 
13  return dp[target]
14}
15 
16console.log(howSum(7, [2, 3]))        // [3, 2, 2]
17console.log(howSum(7, [5, 3, 4, 7]))  // [4, 3]
18console.log(howSum(7, [2, 4]))        // null
19console.log(howSum(8, [2, 3, 5]))     // [2, 2, 2, 2]
20console.log(howSum(300, [7, 14]))     // null
21 
22// time = O(m * n) where n is the length of the array & m is target
23// space = O(m) where m is target

5. Best Sum

Write a function bestSum(target, nums) that takes in a target and an array of numbers as arguments

The function should return an array containing the shortest combination of numbers that add up to exactly the target.

If there is a tie for the shortest combination, you may return any one of the shortest.

1const bestSum = (target, nums) => {
2  if (target === 0) return []
3  if (target < 0) return null
4 
5  let shortestCombination = null
6 
7  for (let n of nums) {
8    const remainder = target - n
9    const remainderCombination = bestSum(remainder, nums)
10    if (remainderCombination !== null) {
11      const comb = [...remainderCombination, n]
12      if (shortestCombination === null || comb.length < shortestCombination.length) {
13        shortestCombination = comb
14      }
15    }
16  }
17  return shortestCombination
18}
19 
20console.log(bestSum(7, [5, 3, 4, 7])) // [7]
21console.log(bestSum(8, [2, 3, 5])) // [3, 5]
22console.log(bestSum(8, [1, 4, 5])) // [4, 4]
23console.log(bestSum(100, [1, 2, 5, 25])) // [25, 25, 25, 25]
24 
25// time = O(nᵗ) where n is the number of elements in nums and t is the target
26// space = O(t) where t is the target

1const bestSum = (target, nums, memo = {}) => {
2  if (target in memo) return memo[target]
3  if (target === 0) return []
4  if (target < 0) return null
5 
6  let smallest = null
7 
8  for (let n of nums) {
9    const remainder = target - n
10    const remainderCombination = bestSum(remainder, nums, memo)
11    if (remainderCombination !== null) {
12      const comb = [...remainderCombination, n]
13      if (smallest === null || comb.length < smallest.length) {
14        smallest = comb
15      }
16    }
17  }
18  memo[target] = smallest
19  return smallest
20}
21 
22console.log(bestSum(7, [5, 3, 4, 7])) // [7]
23console.log(bestSum(8, [2, 3, 5])) // [3, 5]
24console.log(bestSum(8, [1, 4, 5])) // [4, 4]
25console.log(bestSum(100, [1, 2, 5, 25])) // [25, 25, 25, 25]

1const bestSum = (targetSum, nums) => {
2  const table = Array(targetSum + 1).fill(null)
3  table[0] = []
4  for (let i = 0; i < targetSum; i++) {
5    if (table[i] != null) {
6      for (let n of nums) {
7        const newComb = [...table[i], n]
8        if (!table[i + n] || table[i + n].length > newComb.length) {
9          table[i + n] = newComb
10        }
11      }
12    }
13  }
14  return table[targetSum]
15}
16 
17console.log(bestSum(7, [5, 3, 4, 7])) // [7]
18console.log(bestSum(8, [2, 3, 5])) // [3, 5]
19console.log(bestSum(8, [1, 4, 5])) // [4, 4]
20console.log(bestSum(100, [1, 2, 5, 25])) // [25, 25, 25, 25]

6. Can Construct

Write a function canConstruct(target, wordBank) that accepts a target string and an array of strings.

The function should return a boolean indicating whether or not the target can be constructed by concatenating elements of the wordBank array.

You may reuse elements of wordBank as many times as needed.

1const canConstruct = (target, wordBank) => {
2  if (target === '') return true
3 
4  for (let word of wordBank) {
5    if (target.indexOf(word) === 0) {
6      const suffix = target.slice(word.length)
7      if (canConstruct(suffix, wordBank) === true) {
8        return true
9      }
10    }
11  }
12  return false
13}
14 
15console.log(canConstruct('abcdef', ['ab', 'cd', 'ef', 'abc', 'def', 'abcd', 'ef']))
16console.log(canConstruct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar']))
17console.log(canConstruct('potato', ['p', 'ot', 'eo', 'g', 'a', 't']))
18console.log(
19  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
20    'e',
21    'ee',
22    'eee',
23    'eeee',
24    'eeeee',
25    'eeeeee',
26  ])
27)

1const canConstruct = (target, wordBank, memo = {}) => {
2  if (target in memo) return memo[target]
3  if (target === '') return true
4 
5  for (let word of wordBank) {
6    if (target.indexOf(word) === 0) {
7      const suffix = target.slice(word.length)
8      if (canConstruct(suffix, wordBank, memo) === true) {
9        memo[target] = true
10        return true
11      }
12    }
13  }
14  memo[target] = false
15  return false
16}
17 
18console.log(canConstruct('abcdef', ['ab', 'cd', 'ef', 'abc', 'def', 'abcd', 'ef']))
19console.log(canConstruct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar']))
20console.log(canConstruct('potato', ['p', 'ot', 'eo', 'g', 'a', 't']))
21console.log(
22  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
23    'e',
24    'ee',
25    'eee',
26    'eeee',
27    'eeeee',
28    'eeeeee',
29  ])
30)

1const canConstruct = (target, wordBank) => {
2  const table = Array(target.length + 1).fill(false)
3  table[0] = true
4 
5  for (let i = 0; i < target.length; i++) {
6    if (table[i]) {
7      for (let word of wordBank) {
8        if (target.slice(i, i + word.length) === word) {
9          table[i + word.length] = true
10        }
11      }
12    }
13  }
14  return table[target.length]
15}
16 
17console.log(canConstruct('abcdef', ['ab', 'cd', 'ef', 'abc', 'def', 'abcd', 'ef'])) // true
18console.log(canConstruct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar'])) // false
19console.log(canConstruct('potato', ['p', 'ot', 'eo', 'g', 'a', 't', 'o'])) // true
20console.log(
21  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
22    'e',
23    'ee',
24    'eee',
25    'eeee',
26    'eeeee',
27    'eeeeee',
28  ])
29) // false
30 
31// time = o(nm ^ 2)
32// space = o(m)

7. Count Construct

Write a function countConstruct(target, wordBank) that accepts a target string and an array of strings.

The function should return the number of ways that the target can be constructed by concatenating elements of the wordBank array.

You may reuse elements of the word bank as many times as you want.

1const countConstruct = (target, wordBank) => {
2  if (target === '') return 1
3 
4  let totalCount = 0
5 
6  for (let word of wordBank) {
7    if (target.indexOf(word) === 0) {
8      const numWaysForRest = countConstruct(target.slice(word.length), wordBank)
9      totalCount += numWaysForRest
10    }
11  }
12  return totalCount
13}
14 
15console.log(countConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl']))
16console.log(countConstruct('abcdef', ['ab', 'cd', 'ef', 'abc', 'def', 'abcd', 'ef']))
17console.log(countConstruct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar']))
18console.log(countConstruct('potato', ['p', 'ot', 'eo', 'g', 'a', 't']))
19console.log(
20  countConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
21    'e',
22    'ee',
23    'eee',
24    'eeee',
25    'eeeee',
26    'eeeeee',
27  ])
28)

1const countConstruct = (target, wordBank, memo = {}) => {
2  if (target in memo) return memo[target]
3  if (target === '') return 1
4 
5  let totalCount = 0
6 
7  for (let word of wordBank) {
8    if (target.indexOf(word) === 0) {
9      const numWaysForRest = countConstruct(target.slice(word.length), wordBank, memo)
10      totalCount += numWaysForRest
11    }
12  }
13  memo[target] = totalCount
14  return totalCount
15}
16 
17console.log(countConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl']))
18console.log(countConstruct('abcdef', ['ab', 'cd', 'ef', 'abc', 'def', 'abcd', 'ef']))
19console.log(countConstruct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar']))
20console.log(countConstruct('potato', ['p', 'ot', 'eo', 'g', 'a', 't']))
21console.log(
22  countConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
23    'e',
24    'ee',
25    'eee',
26    'eeee',
27    'eeeee',
28    'eeeeee',
29  ])
30)

1const countConstruct = (target, wordBank) => {
2  const table = Array(target.length + 1).fill(0)
3  table[0] = 1
4 
5  for (let i = 0; i < target.length; i++) {
6    for (const word of wordBank) {
7      if (target.slice(i, i + word.length) === word) {
8        table[i + word.length] += table[i]
9      }
10    }
11  }
12 
13  return table[target.length]
14}
15 
16console.log(countConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl'])) // 2
17console.log(countConstruct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd'])) // 1
18console.log(countConstruct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar'])) // 0
19console.log(countConstruct('potato', ['p', 'ot', 'eo', 'g', 'a', 't']))
20console.log(
21  countConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
22    'e',
23    'ee',
24    'eee',
25    'eeee',
26    'eeeee',
27    'eeeeee',
28  ])
29)

8. All Construct

Write a function allConstruct(target, wordBank) that accepts a target string and an array of strings.

The function should return a 2D array containing all of the ways that the target can be constructed by concatenating elements of the wordBank array.

1const allConstruct = (target, wordBank) => {
2  if (target === '') return [[]]
3 
4  const result = []
5 
6  for (let word of wordBank) {
7    if (target.indexOf(word) === 0) {
8      const suf = target.slice(word.length)
9      const suffixWays = allConstruct(suf, wordBank)
10      const targetWays = suffixWays.map((way) => [word, ...way])
11      result.push(...targetWays)
12    }
13  }
14  return result
15}
16 
17console.log(allConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl']))
18// [
19//   ['purp', 'le'],
20//   ['p', 'ur', 'p', 'le'],
21// ]
22console.log(allConstruct('hello', ['dog', 'cat', 'mouse']))
23// []
24console.log(allConstruct('', ['dog', 'cat', 'mouse']))
25// [[]]

1const allConstruct = (target, wordBank, memo = {}) => {
2  if (target in memo) return memo[target]
3  if (target === '') return [[]]
4 
5  const result = []
6 
7  for (let word of wordBank) {
8    if (target.indexOf(word) === 0) {
9      const suf = target.slice(word.length)
10      const suffixWays = allConstruct(suf, wordBank, memo)
11      const targetWays = suffixWays.map((way) => [word, ...way])
12      result.push(...targetWays)
13    }
14  }
15  memo[target] = result
16  return result
17}
18 
19console.log(allConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl']))
20// [
21//   ['purp', 'le'],
22//   ['p', 'ur', 'p', 'le'],
23// ]
24console.log(allConstruct('hello', ['dog', 'cat', 'mouse']))
25// []
26console.log(allConstruct('', ['dog', 'cat', 'mouse']))
27// [[]]

1const allConstruct = (target, wordBank) => {
2  const table = Array(target.length + 1)
3    .fill()
4    .map(() => [])
5  table[0] = [[]]
6 
7  for (let i = 0; i < target.length; i++) {
8    for (const word of wordBank) {
9      if (target.slice(i, i + word.length) === word) {
10        const newComb = table[i].map((arr) => [...arr, word])
11        table[i + word.length].push(...newComb)
12      }
13    }
14  }
15  return table[target.length]
16}
17 
18console.log(allConstruct('fish', ['dog', 'cat', 'mouse'])) // [[]]
19console.log(allConstruct('bird', ['bi', 'rd', 'do', 'g'])) // [ [ 'bi', 'rd' ] ]
20console.log(allConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl']))
21// [
22//   ['purp', 'le'],
23//   ['p', 'ur', 'p', 'le'],
24// ]
25console.log(allConstruct('ape', ['a', 'p', 'e', 'ap', 'pe']))
26// [ [ 'purp', 'le' ], [ 'p', 'ur', 'p', 'le' ] ]
27// []
28// [ [] ]
29// [ [ 'a', 'pe' ], [ 'ap', 'e' ], [ 'a', 'p', 'e' ] ]

Conclusion

The covered DP patterns & a few more advanced ones.

Approach	Recursion	Table/Cache	Space	Time
Top-Down (Memoization)	✅	✅	O(n) or more	O(n)
Bottom-Up (Tabulation)	❌	✅	O(n)	O(n)
Bottom-Up + Space Optimization	❌	✅ (partial)	O(1)	O(n)
Matrix Exponentiation	❌	✅ (implicit)	O(1)	O(log n)
Bitmask DP	✅/❌	✅	O(2ⁿ·n)	O(2ⁿ·n)
Recursive DP + Pruning	✅	✅/❌	varies	varies