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

Dãy Fibonacci bắt đầu bằng 0, 1 (hoặc 1, 1) và mỗi số tiếp theo là tổng của hai số trước. Phương pháp Bottom-Up giải quyết các bài toán con nhỏ trước rồi kết hợp thành giải pháp hoàn chỉnh.

Độ 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 FibonacciBottomupApproach(int n)
    {
        int[] dpArr = new int[150];
        dpArr[0] = 0;
        dpArr[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            dpArr[i] = dpArr[i - 1] + dpArr[i - 2];
        }
        return dpArr[n];
    }
}

static void Main(string[] args)
{
    DynamicProgramming dp = new DynamicProgramming();
    Console.WriteLine(dp.FibonacciBottomupApproach(5)); // Output: 5
}

Kết quả đầu ra

5

Lưu ý: Code gốc khởi tạo dpArr[1] = 1 nhưng không set dpArr[0]. Phiên bản trên đã bổ sung dpArr[0] = 0 để đúng định nghĩa Fibonacci chuẩn.