Cách triển khai dãy Fibonacci bằng phương pháp Top-Down trong C#

Dãy Fibonacci: mỗi số là tổng hai số trước. Phương pháp Top-Down chia bài toán lớn thành các bài toán con nhỏ hơn. Độ phức tạp không gian O(N) do tạo mảng nhớ đệm.

Độ phức tạp thời gian: O(N)

Độ phức tạp không gian: O(N)

Ví dụ

public class DynamicProgramming
{
    public int FibonacciTopdownApproach(int n, int[] dpArr)
    {
        if (n == 0 || n == 1)
        {
            return n;
        }
        if (dpArr[n] != 0)
        {
            return dpArr[n];
        }
        int res = FibonacciTopdownApproach(n - 1, dpArr) + FibonacciTopdownApproach(n - 2, dpArr);
        return dpArr[n] = res;
    }
}

static void Main(string[] args)
{
    DynamicProgramming dp = new DynamicProgramming();
    int[] dpArr = new int[150];
    Console.WriteLine(dp.FibonacciTopdownApproach(12, dpArr)); // Output: 144
}

Kết quả đầu ra

144