Overlapping Subproblems

In dynamic programming, overlapping subproblems refer to the phenomena where the solution to a problem can be generated by solving the same subproblem multiple times. This repetition of subproblems leads to redundant computations, causing inefficiency in solving the problem.

To avoid recomputation of the same subproblems, a technique called memoization is used. Memoization involves storing the solutions to subproblems in a cache or memo table, so that they can be directly retrieved when needed.

For example, let's consider the Fibonacci sequence. The Fibonacci sequence is a classic example of overlapping subproblems. The Fibonacci number at index n can be calculated by summing the Fibonacci numbers at indices n-1 and n-2. However, if we use a naive recursive approach to calculate Fibonacci numbers, we end up recalculating the same Fibonacci numbers multiple times.

Here's an example of calculating the nth Fibonacci number using memoization:

1function fibonacci(n) {
2  const memo = {};
3
4  function fib(n) {
5    if (n <= 2) {
6      return 1;
7    }
8
9    if (memo[n]) {
10      return memo[n];
11    }
12
13    const result = fib(n - 1) + fib(n - 2);
14    memo[n] = result;
15    return result;
16  }
17
18  return fib(n);
19}
20
21console.log(fibonacci(6)); // Output: 8

xxxxxxxxxx

// replace with relevant JS code

​

function fibonacci(n) {

  const memo = {};

​

  function fib(n) {

    if (n <= 2) {

      return 1;

    }

​

    if (memo[n]) {

      return memo[n];

    }

​

    const result = fib(n - 1) + fib(n - 2);

    memo[n] = result;

    return result;

  }

​

  return fib(n);

}

​

console.log(fibonacci(6)); // Output: 8