การคำนวณเลขฟีโบนัชชีด้วยวิธี Top-Down ใน C#

ลำดับฟีโบนัชชี เริ่มจาก 0 และ 1 ตัวต่อไปเท่ากับผลรวมสองตัวก่อนหน้า วิธี Top-Down แบ่งปัญหาใหญ่เป็นชิ้นเล็กๆ ที่เข้าใจง่าย Space Complexity เป็น O(N) เนื่องจากสร้างอาร์เรย์เพิ่มขนาดเท่ากับ n

Time Complexity: O(N)

Space Complexity: O(N)

ตัวอย่างโค้ด

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));
}

ผลลัพธ์

144