ลำดับฟีโบนักชีคือชุดของตัวเลขที่ขึ้นต้นด้วยหนึ่งหรือศูนย์ ตามด้วยหนึ่ง และดำเนินการตามกฎที่แต่ละหมายเลข (เรียกว่าหมายเลขฟีโบนักชี) เท่ากัน เป็นผลรวมของตัวเลขสองตัวก่อนหน้า วิธีการจากบนลงล่างมุ่งเน้นไปที่การแยกปัญหาใหญ่ออกเป็นชิ้นเล็ก ๆ และเข้าใจได้ ความซับซ้อนของพื้นที่คือ O(N) เนื่องจากเรากำลังสร้างหน่วยความจำอาร์เรย์พิเศษซึ่งเท่ากับขนาดของตัวเลข
ความซับซ้อนของเวลา − O(N)
ความซับซ้อนของอวกาศ − 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
