Programming is a field that attracts many aspiring individuals, but often programmers tend to overlook certain fundamental concepts. One such fundamental concept is dynamic programming.
At first glance, the term "dynamic programming" might be mistaken for a programming approach that dynamically adjusts itself in real-time. However, once you delve into the concepts of dynamic programming, you'll realize that it is actually an optimization approach to solving programming problems.
What is JavaScript Dynamic Programming?
Dynamic programming is an optimization approach to solving algorithmic problems. It is both a mathematical optimization method and a computer programming method that was developed by Richard Bellman in the 1950s. Dynamic programming has applications in various fields, including aerospace engineering and economics.
In simple terms, JavaScript dynamic programming is an approach to solving algorithmic problems in a way that provides a more efficient solution compared to a naive solution that involves recursion, in most cases.
However, not every algorithmic problem can be efficiently solved using dynamic programming. There are certain conditions that must be met for a problem to be solved using this approach:
The problem can be solved recursively by breaking it down into smaller sub-problems and solving each of them individually.
The subproblems must overlap at some point. This means that solving the main problem involves solving the same sub-problem multiple times.
Approaches to Solve a Problem
Dynamic programming can be used to solve a problem through two major approaches.
Top-down approach with Memoization
Bottom-up approach with Tabulation
1. Top-down approach with Memoization: In this approach, the problem is solved by recursively breaking it down into smaller sub-problems. These sub-problems are solved one by one. To avoid redundant calculations of the same sub-problems, the results of each sub-problem are stored in a cache or temporary memory store. This technique of storing computed results is called memoization. By utilizing memoization, the time spent on computing the result is reduced, as the stored values can be retrieved from previous computations of the same sub-problems.
2. Bottom-up approach with Tabulation: Unlike the top-down approach, the bottom-up approach avoids recursion. Instead of starting with the main problem, it begins solving the sub-problems and gradually builds up toward the main problem. In this approach, a table of n-dimensions, known as tabulation, is used to store intermediate results. These results stored in the table are then used to compute the final output for the original problem.
Understanding With the Help of Ugly Numbers
To better understand dynamic programming, let's take a look at an example problem: finding ugly numbers. Ugly numbers are numbers whose prime factors are only 2, 3, or 5. For instance, the sequence of ugly numbers begins with 1, followed by 2, 3, 4, 5, 6, and so on. Given a number n, the task is to find the nth ugly number.
Types of approaches to solving a problem
1. Brute Force
This approach involves looping through an infinite range of numbers and checking if each number is an ugly number. If an ugly number is found, a counter is incremented to keep track of the number of ugly numbers found. However, this approach is straightforward and not very efficient.
This is a very straightforward approach.
const isUgly = num => {
while (num !== 1) {
if (num % 2 === 0) {
num /= 2;
} else if (num % 3 === 0) {
num /= 3;
} else if (num % 5 === 0) {
num /= 5;
} else {
return false;
};
};
return true;
};
const getNthUglyNo = (n) => {
let i = 1;
let count = 1;
while (n > count) {
i++;
if (isUgly(i)) {
count++;
}
}
return i;
}
console.log("100th Ugly number", getNthUglyNo(100));
//100th Ugly number => 15362. Brute Force — Recursion(a.k.a Top-down approach)
Similar to the brute force approach, this method uses recursion instead of a loop. The problem is solved by recursively checking if a number is an ugly number. Although it is a top-down approach, it suffers from inefficiency due to redundant calculations.
This is a very similar approach to the above, but instead of looping within the while loop, we use recursion.
const getNthUglyNo = (n) => {
let i = 1;
let count = 1;
while (n > count) {
i++;
if (isUgly(i)) {
count++;
}
}
return i;
}
const isUgly = num => {
if (num !== 1) {
if (num % 2 === 0) {
return isUgly(num / 2);
} else if (num % 3 === 0) {
return isUgly(num / 3);
} else if (num % 5 === 0) {
return isUgly(num / 5);
} else {
return false;
};
};
return true;
};
console.log("100th Ugly number => ", getNthUglyNo(100));When using a top-down approach, we begin by solving the main problem and then delve into the sub-problems, solving them iteratively. Since this approach involves recursion, the solution to the main problem incorporates the solutions obtained from the sub-problems. Therefore, we proceed from the top-down to solve the main problem.
3. Top-down with Memoization
This approach builds upon the previous method by integrating memoization. The results of computed sub-problems are stored in a cache, and if the same sub-problem is encountered again, the cached result is retrieved. By doing so, the top-down approach with memoization saves computational time by avoiding redundant calculations.
Have a look at the code below.
var hits = 0;
const getNthUglyNo = (n) => {
let i = 1;
let count = 1;
while (n > count) {
i++;
if (isUgly(i)) {
count++;
}
}
return i;
}
let isUgly = num => {
if (num !== 1) {
if (num % 2 === 0) {
return isUgly(num / 2);
} else if (num % 3 === 0) {
return isUgly(num / 3);
} else if (num % 5 === 0) {
return isUgly(num / 5);
} else {
return false;
};
};
return true;
};
const memoize = fn => {
let cache = {};
return (num) => {
if (num in cache) {
//console.log("Taken from cache", num);
hits++;
return cache[num];
} else {
//console.log("Result calculated", num)
let result = fn(num);
cache[num] = result;
return result;
}
}
}
isUgly = memoize(isUgly);
console.log("100th Ugly number", getNthUglyNo(100));
console.log("Cache hits => ", hits);
//100th Ugly number 1536
//Cache hits => 1126Furthermore, it is worth mentioning that we accessed cached values 1126 times. This indicates that the top-down approach with memoization has effectively eliminated the need for 1126 redundant computations, which would have been required in the previous approach without memoization.
4. Bottom-up with Tabulation
In this approach, a different strategy is employed. By observing the sequence of ugly numbers, it becomes apparent that they can be divided into subsequences based on multiples of 2, 3, and 5. By selecting the smallest ugly number from these subsequences at each step, we can ensure that no ugly numbers are missed. This bottom-up approach, using tabulation to store intermediate results, offers an efficient solution to the problem.
Let’s have a look at our solution now.
const getNthUglyNo = (num) => {
let uglyNumbers = [];
let i2 = 0,i3 = 0,i5 = 0;
let nextMultipleOf2 = 2;
let nextMultipleOf3 = 3;
let nextMultipleOf5 = 5;
let nextUglyNo = 1;
uglyNumbers.push(1);
for (let i = 1; i < num; i++) {
nextUglyNo = Math.min(nextMultipleOf2, nextMultipleOf3, nextMultipleOf5);
uglyNumbers.push(nextUglyNo);
if (nextUglyNo === nextMultipleOf2) {
i2++;
nextMultipleOf2 = uglyNumbers[i2] * 2;
}
if (nextUglyNo === nextMultipleOf3) {
i3++;
nextMultipleOf3 = uglyNumbers[i3] * 3;
}
if (nextUglyNo === nextMultipleOf5) {
i5++;
nextMultipleOf5 = uglyNumbers[i5] * 5;
}
}
return nextUglyNo;
}
console.log("100th Ugly number => ", getNthUglyNo(100));
//100th Ugly number => 1536The code is implementing a function called getNthUglyNo that calculates the nth ugly number. Ugly numbers are defined as numbers whose prime factors are only 2, 3, or 5.
Here's how the code works:
It initializes an empty array called uglyNumbers to store the ugly numbers.
It declares and initializes variables i2, i3, and i5 to keep track of the indices for the multiples of 2, 3, and 5 respectively.
It declares variables nextMultipleOf2, nextMultipleOf3, and nextMultipleOf5 to store the next multiples of 2, 3, and 5 respectively.
It initializes nextUglyNo to 1, as the first ugly number, and adds it to the uglyNumbers array.
The code then enters a loop starting from i = 1 and continues until i reaches num, the input parameter.
Inside the loop, it finds the minimum value among nextMultipleOf2, nextMultipleOf3, and nextMultipleOf5, and assigns it to nextUglyNo.
The nextUglyNo is added to the uglyNumbers array.
The code checks if nextUglyNo is equal to nextMultipleOf2, nextMultipleOf3, or nextMultipleOf5, and if so, it increments the respective index (i2, i3, or i5) and updates the corresponding next multiple by multiplying the ugly number at the incremented index by 2, 3, or 5 respectively.
The loop continues until i reaches num, and then it returns the last calculated nextUglyNo.
Finally, the code calls the getNthUglyNo function with an argument of 100 and prints the result using console.log.
In this specific example, the code calculates and prints the 100th ugly number, which is 1536.
Comparison
Comparing the performance of these approaches, it becomes evident that dynamic programming techniques yield more efficient solutions compared to brute force methods.
Tabulation, in particular, is often faster than memoization because it is an iterative process that avoids recursion overhead. However, tabulation may require going through the entire search space, making it harder to optimize runtime. In certain cases, memoization may be preferred over tabulation.
Dynamic programming is a powerful technique that can greatly enhance the efficiency of algorithmic problem-solving. By understanding the principles behind dynamic programming and applying the appropriate approach, programmers can tackle complex problems with improved performance.