Space Optimization

In the bottom-up dynamic programming approach for the Fibonacci sequence, we can further optimize the approach to use constant space instead of an array or table to store the previously calculated Fibonacci numbers.

Instead of storing all the Fibonacci numbers, we only need to keep track of the last two Fibonacci numbers for the current calculation. We can use two variables to store these numbers and update them as we iterate through the sequence.

Here's an example of the space-optimized bottom-up dynamic programming approach for the Fibonacci sequence in C#:

1public class Fibonacci
2{
3    public static int GetFibonacci(int n)
4    {
5        if (n == 0)
6            return 0;
7        
8        if (n == 1)
9            return 1;
10        
11        int prev = 0;
12        int curr = 1;
13        
14        for (int i = 2; i <= n; i++)
15        {
16            int temp = curr;
17            curr = prev + curr;
18            prev = temp;
19        }
20        
21        return curr;
22    }
23}
24
25// Example usage:
26int fibonacciNumber = Fibonacci.GetFibonacci(5);
27Console.WriteLine(fibonacciNumber);

xxxxxxxxxx

public class Fibonacci

{

    public static int GetFibonacci(int n)

    {

        if (n == 0)

            return 0;

        if (n == 1)

            return 1;

        int[] dp = new int[2];

        dp[0] = 0;

        dp[1] = 1;

        for (int i = 2; i <= n; i++)

        {

            int temp = dp[1];

            dp[1] = dp[0] + dp[1];

            dp[0] = temp;

        }

        return dp[1];

    }

}

​

// Example usage:

int fibonacciNumber = Fibonacci.GetFibonacci(5);

Console.WriteLine(fibonacciNumber);