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

피보나치 수열은 1 또는 0으로 시작하고 그 뒤에 1이 오는 일련의 숫자로, 각 숫자(피보나치 수라고 함)가 동일하다는 규칙에 따라 진행됩니다. 앞의 두 숫자의 합으로. 상향식 접근 방식은 먼저 근본적인 수준에서 작은 문제를 해결한 다음 전체적이고 완전한 솔루션으로 통합하는 데 중점을 둡니다.

시간 복잡도 - 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