Top-down Dynamic Programming

In the previous screen, we implemented a recursive solution for the Fibonacci sequence. However, the recursive approach has overlapping subproblems, resulting in redundant calculations. To optimize the recursive solution, we can use a technique called top-down dynamic programming.

Top-down dynamic programming, also known as memoization, involves storing the results of expensive function calls and reusing them when the same inputs occur again. This approach reduces the time complexity by avoiding redundant computations and improves the efficiency of the solution.

To implement top-down dynamic programming for the Fibonacci sequence, we can create a memoization table to store the previously calculated Fibonacci numbers. Here's an example of how to modify the recursive solution using memoization in C#:

xxxxxxxxxx

public class Fibonacci

{

    private static int[] memo;

​

    public static int FibonacciMemoization(int n)

    {

        memo = new int[n + 1];

        return FibonacciMemoizationHelper(n);

    }

​

    private static int FibonacciMemoizationHelper(int n)

    {

        if (n == 0) return 0;

        if (n == 1) return 1;

​

        if (memo[n] != 0) return memo[n];

​

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

​

        return memo[n];

    }

}

​

Console.WriteLine(Fibonacci.FibonacciMemoization(6));