Fibonacci Numbers

As a senior engineer interested in practice data structures and algorithms, you may be familiar with the concept of the Fibonacci sequence, which is a series of numbers where each number is the sum of the two preceding ones.

In the context of dynamic programming, we can use a technique called memoization to efficiently compute Fibonacci numbers and avoid redundant computations.

Let's consider the problem of computing the n-th Fibonacci number. The naive recursive approach to solve this problem has exponential time complexity since it solves the same subproblems multiple times. However, by using memoization, we can store the results of subproblems and reuse them when needed, resulting in a more efficient solution.

Here's an implementation of the Fibonacci function using memoization in Java:

1class Main {
2  public static void main(String[] args) {
3    // replace with your Java logic here
4    int result = fibonacci(6);
5    System.out.println("The 6th Fibonacci number is: " + result);
6  }
7
8  private static int fibonacci(int n) {
9    int[] memo = new int[n + 1];
10    return fibonacciHelper(n, memo);
11  }
12
13  private static int fibonacciHelper(int n, int[] memo) {
14    if (n <= 1) {
15      return n;
16    }
17
18    if (memo[n] != 0) {
19      return memo[n];
20    }
21
22    memo[n] = fibonacciHelper(n - 1, memo) + fibonacciHelper(n - 2, memo);
23    return memo[n];
24  }
25}

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

    int result = fibonacci(6);

    System.out.println("The 6th Fibonacci number is: " + result);

  }

​

  private static int fibonacci(int n) {

    int[] memo = new int[n + 1];

    return fibonacciHelper(n, memo);

  }

​

  private static int fibonacciHelper(int n, int[] memo) {

    if (n <= 1) {

      return n;

    }

​

    if (memo[n] != 0) {

      return memo[n];

    }

​

    memo[n] = fibonacciHelper(n - 1, memo) + fibonacciHelper(n - 2, memo);

    return memo[n];

  }

}