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