মডিউল ১৭_৭ঃ Bottom up approach in Fibonacci series

আমরা এতক্ষন যে এপ্রোচ বা memoization মেথড দেখেছি সেটাকে বলা হয় top down approach| আমরা এখন bottom up এপ্রোচ দেখবো।

ব্যাপারটা হচ্ছে আমরা top down এর ক্ষেত্রে n দেওয়া থাকলে সেখান থেকে ক্যালকুলেশন শুরু করে ০ অব্দি যেতাম।

n->n-1->n-2->...........->3->2->1

এখন আমরা ০ থেকে ক্যালকুলেট করে n এর কাছে যাবো।

0->1->2->3->..........->n-2->n-1->n

আমরা বিষয়টা করবো একটা এ্যারে এর মাধ্যমে।

একটা এ্যারে নিব এবং সেখানে ০ আর ১ এর ভ্যালু যথাক্রমে ০ আর ১ সেট করে দিব।

তারপর যাস্ট একটা কাজ করবো। সেটা হচ্ছে

a[i] = a[i-1]+a[i-2]

এভাবেই Bottoum up approach এ fibonacci number ক্যাল্কুলেট করা হয়।

সম্পূর্ণ কোডঃ

// Some code
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n];
    a[0] = 0;
    a[1] = 1;
    // O(N)
    for (int i = 2; i <= n; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
    }
    cout << a[n] << endl;
    return 0;
}