ফিবোনাচি সিকোয়েন্স হল সংখ্যার একটি সেট যা একটি এক বা শূন্য দিয়ে শুরু হয়, একটির পরে একটি, এবং প্রতিটি সংখ্যা (একটি ফিবোনাচি সংখ্যা বলা হয়) সমান হওয়ার নিয়মের উপর ভিত্তি করে এগিয়ে যায় পূর্ববর্তী দুটি সংখ্যার সমষ্টিতে। টপ-ডাউন পদ্ধতিটি একটি বড় সমস্যাকে ছোট এবং বোধগম্য অংশে ভাঙ্গার উপর ফোকাস করে। স্থান জটিলতা হল 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
