Làm thế nào để triển khai Fibonacci bằng cách sử dụng phương pháp topDown bằng C #?

Dãy Fibonacci là một tập hợp các số bắt đầu bằng một hoặc một số 0, sau đó là một số và tiến hành dựa trên quy tắc mỗi số (được gọi là số Fibonacci) bằng nhau thành tổng của hai số trước đó. Cách tiếp cận từ trên xuống tập trung vào việc chia nhỏ một vấn đề lớn thành các phần nhỏ hơn và dễ hiểu. Độ phức tạp của không gian là O (N) bởi vì chúng tôi đang tạo thêm một bộ nhớ mảng bằng với kích thước của số.

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

Độ phức tạp của 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));
}

Đầu ra

144