Beginner’s Guide to Dynamic Programming

If you have been programming for a long time, then you may have heard about the term “dynamic programming”. Most often this term pops up in technical interviews, also appears when discussing the design of the system or when communicating with other developers. This article will look at what dynamic programming is and why you should use it. I will illustrate this concept with specific examples of JavaScript code, but any other programming language can be used instead. Let’s start!

way of thinking

Unlike certain code syntax or design patterns, dynamic programming is not a specific algorithm, but a way of thinking. Therefore, there is no single way to implement this technique. The main idea of ​​dynamic programming is to consider the main problem and break it down into smaller individual components. When implementing for the efficient operation of the algorithm, the technique of storing and reusing already calculated data is used. As we will see, most software development problems are solved using various forms of dynamic programming. The trick is to recognize when the optimal solution can be developed using a simple variable and when using complex data structures and algorithms.

For example, variables in code can be considered an elementary form of dynamic programming. As we know, the purpose of a variable is to reserve a certain place in memory for a value that will be called later.

// не-мемоизированная функция
function addNumbers(lhs, rhs) {
  return lhs + rhs;
}

// мемоизированная функция
function addNumbersMemo(lhs, rhs) {
  const result = lhs + rhs;
  return result;
}

In the code above, the function addNumbersMemo is a basic example. The main purpose of using dynamic programming is to preserve the value of the previous calculation, because the alternative solution will either be inefficient or may prevent you from solving the problem. This design technique is known as memoization.

Solving the problem “Pair of numbers”

Over the years, I’ve had the opportunity to do mock interviews with dozens of developers preparing for FAANG interviews. Most of us would be happy to skip chalkboard problems or tests. However, many of these tasks are designed to test a basic understanding of basic computer science. Consider the following problem:

/*
На техническом собеседование вам дан массив целых чисел, необходимо найти пару таких чисел, сумма которых равна заданному значению. 
Числа в массиве могут быть положительными и отрицительными. Можете ли вы разработать алгоритм, который решает задачу за O(n)—линейное время?

const sequence = [8, 10, 2, 9, 7, 5]
const results = pairValues(11) // returns [9, 2]
*/

There are several ways to solve the problem. In this case, the goal is to find out which numbers need to be paired to get the desired result. If you try to solve the problem in your head, it is easy to look through the sequence of numbers and find a pair of 9 and 2. When developing a working program algorithm, the first thing that comes to mind is that we should check each number in the sequence and compare it with the rest. However, there is a more optimized algorithm. Let’s consider both.

brute force

The first approach to the solution is to look at the first number in the sequence and calculate the difference from the given number, and then look at each subsequent number to determine if the difference is equal to the current number. For example, the first value of our sequence will be 8, and the difference with a given number is 3 (11 – 8 = 3), then the algorithm will scan other numbers for equality with a difference. As we can see, there is no number 3 in our sequence, so the algorithm will repeat the same work with the next number in the sequence (which is 10). The algorithm will work until it finds the desired pair of numbers or the sequence ends. Without going into the details of the big O notation, we can assume that the average execution time of the algorithm will be O(n^2), because every number in the sequence is compared with every other number in the sequence. Implementation example:

const sequence = [8, 10, 2, 9, 7, 5]
// не-мемоизированная версия - O(n ^ 2)
function pairNumbers(sum) {
	for (let a of sequence) {
		const diff = sum - a;

		for (let b of sequence) {
			if (b !== a && b === diff) {
				return [a, b]
			}
		}
	}

	return [0, 0]
}

Using Memoization

Let’s try a different approach using memoization. Before proceeding with the implementation, let’s think about how storing previously viewed numbers will help us optimize the algorithm. You can use a Set value collection object to store the scanned numbers, which is faster than using an array.

// мемоизированная функция - O(n + d)
function pairNumbersMemoized(sum) {
	const addends = new Set();
    
	for (let a of sequence) {
		const diff = sum - a;
   	 
    if (addends.has(diff)) { // O(1) - константа
			return [a, diff]
		} else { // сохраняем текущее число
			addends.add(a)
		}
	}
    
	return [0, 0]
}

Using memoization, we improved the average time of the algorithm to O(n + d) by adding previously seen values ​​to the Set collection. The Set object uses the data structure in hash tablesthat’s why insert and receive speed values ​​occurs in O(1).

Fibonacci numbers

When studying various programming techniques, one may come across such a topic as recursion. Recursive solutions work by having a model that refers to itself. A well-known example of recursion can be seen in the Fibonacci sequence, a numerical sequence obtained by adding two preceding numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, etc.):

function fibRec(n) {
  if (n < 2) {
    return n;
  } else {
    return fibRec(n - 1) + fibRec(n - 2);
  }
}

When tested, our code works without errors and correctly. However, pay attention to the performance of our algorithm: