C#을 사용하여 topDown 접근 방식을 사용하여 피보나치를 구현하는 방법은 무엇입니까?

피보나치 수열은 1 또는 0으로 시작하고 그 뒤에 1이 오는 일련의 숫자로, 각 숫자(피보나치 수라고 함)가 동일하다는 규칙에 따라 진행됩니다. 앞의 두 숫자의 합으로. 하향식 접근 방식은 큰 문제를 작고 이해할 수 있는 덩어리로 나누는 데 중점을 둡니다. 공간 복잡도는 숫자 크기와 동일한 추가 배열 메모리를 생성하기 때문에 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