Dynamic Programming in JavaScript

Dynamic programming is a technique used in computer science to solve complex problems efficiently by breaking them down into smaller subproblems and storing the solutions in a table or matrix. In this guide, we will explore dynamic programming in-depth, discussing its principles, common techniques, and applications in JavaScript.

Principles of Dynamic Programming

Dynamic programming is based on two principles: optimal substructure and overlapping subproblems.

Optimal substructure means that an optimal solution to a larger problem can be found by combining optimal solutions to smaller subproblems.

Overlapping subproblems refer to the fact that the same subproblems are encountered repeatedly in a problem.

Dynamic programming takes advantage of these two principles to solve problems in an efficient manner, by breaking down a problem into smaller subproblems, solving them, and storing their solutions in a table or matrix. The solutions are then combined to solve the larger problem.

Dynamic Programming Techniques

There are two main techniques used in dynamic programming: top-down (memoization) and bottom-up (tabulation).

Top-down dynamic programming, also known as memoization, involves breaking down a problem into smaller subproblems and storing the solutions to these subproblems in a table or matrix. When solving the larger problem, the solutions to the subproblems are looked up in the table or matrix to avoid redundant computation.

Bottom-up dynamic programming, also known as tabulation, involves solving the subproblems first and storing their solutions in a table or matrix. The solutions to the larger problem are then computed using the solutions to the subproblems.

Common Dynamic Programming Problems

1. Fibonacci Sequence

The Fibonacci sequence is a sequence of numbers where each number is the sum of the two preceding numbers. The sequence begins with 0 and 1, and each subsequent number is the sum of the two preceding numbers.

In dynamic programming, we can compute the nth Fibonacci number efficiently by breaking down the problem into smaller subproblems and storing their solutions in a table or matrix.

Here is an example of computing the nth Fibonacci number using bottom-up dynamic programming in JavaScript:

function fibonacci(n) {
  if (n < 2) {
    return n;
  }

  let table = [0, 1];

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  return table[n];
}

In this example, we start by checking if n is less than 2. If it is, we simply return n. If not, we create a table with the first two Fibonacci numbers (0 and 1). We then use a loop to compute the next n — 1 Fibonacci numbers and store them in the table. Finally, we return the nth Fibonacci number, which is the last element in the table.

2. Longest Increasing Subsequence

The longest increasing subsequence problem involves finding the longest subsequence of a given sequence that is strictly increasing.

In dynamic programming, we can solve this problem efficiently by breaking it down into smaller subproblems and storing their solutions in a table or matrix.

Here is an example of computing the longest increasing subsequence using bottom-up dynamic programming in JavaScript:

function longestIncreasingSubsequence(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

In this example, we start by initializing an array dp with all elements set to 1, since every element in the sequence is a subsequence of length 1. We then use a nested loop to compare every pair of elements in the sequence. If the element at index j is less than the element at index i, we update the value of dp[i] to be the maximum of its current value and dp[j] + 1. This means that we consider extending the subsequence that ends at index j with the element at index i, and take the maximum length of all such subsequence extensions. Finally, we return the maximum value in the dp array, which is the length of the longest increasing subsequence.

Dynamic Programming Algorithms

1. Memoization

Memoization is a top-down dynamic programming technique that involves breaking down a problem into smaller subproblems and storing the solutions to these subproblems in a table or matrix. When solving the larger problem, the solutions to the subproblems are looked up in the table or matrix to avoid redundant computation.

Here is an example of computing the nth Fibonacci number using memoization in JavaScript:

function fibonacci(n, memo = {}) {
  if (n in memo) {
    return memo[n];
  }

  if (n < 2) {
    return n;
  }

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

In this example, we start by checking if n is already in the memoization table. If it is, we return its value. If not, we compute the nth Fibonacci number recursively by recursively computing the (n-1)th and (n-2)th Fibonacci numbers, and storing their sum in the memoization table. This ensures that we only compute each Fibonacci number once, and subsequent calls for the same number will be retrieved from the memoization table.

2. Tabulation

Tabulation is a bottom-up dynamic programming technique that involves solving the subproblems first and storing their solutions in a table or matrix. The solutions to the larger problem are then computed using the solutions to the subproblems.

Here is an example of computing the nth Fibonacci number using tabulation in JavaScript:

function fibonacci(n) {
  if (n < 2) {
    return n;
  }

  let table = [0, 1];

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  return table[n];
}

In this example, we start by checking if n is less than 2. If it is, we simply return n. If not, we create a table with the first two Fibonacci numbers (0 and 1). We then use a loop to compute the next n — 1 Fibonacci numbers and store them in the table. Finally, we return the nth Fibonacci number, which is the last element in the table.

Conclusion

Dynamic programming is a powerful technique used to solve complex problems efficiently by breaking them down into smaller subproblems and storing their solutions in a table or matrix. In JavaScript, dynamic programming can be implemented using memoization or tabulation, depending on the problem at hand. Some common problems that can be solved using dynamic programming include the Fibonacci sequence and the longest increasing subsequence. By understanding the principles and techniques of dynamic programming, you can solve a wide range of problems efficiently and effectively.