ลำดับฟีโบนักชีคือชุดของตัวเลขที่เริ่มต้นด้วยหนึ่งหรือศูนย์ ตามด้วยหนึ่ง และดำเนินการตามกฎที่แต่ละหมายเลข (เรียกว่าหมายเลขฟีโบนักชี) เท่ากัน เป็นผลรวมของตัวเลขสองตัวก่อนหน้า วิธีจากล่างขึ้นบนจะเน้นที่การแก้ปัญหาเล็กๆ น้อยๆ ในระดับพื้นฐานก่อน จากนั้นจึงรวมเข้าเป็นโซลูชันที่สมบูรณ์และครบถ้วน
ความซับซ้อนของเวลา − O(N)
ความซับซ้อนของอวกาศ − O(N)
ตัวอย่าง
public class DynamicProgramming{
public int fibonacciBottomupApproach(int n){
int[] dpArr = new int[150];
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));
} ผลลัพธ์
5
