মডিউল ১৭_৬ঃ Fibonacci Memoization

আমরা আগের পার্টে সাবপ্রবলেম আইডেন্টিফাই করেছিলাম এবং বলেছিলাম যদি যেকোনো একটা সাবপ্রবলেম এর ভ্যালু ক্যালকুলেট করে আমরা সেইভ করে রাখি তাহলে সেই রিপিটেড সাবপ্রবলেম এর জন্য সেটা আবার ক্যালকুলেট করতে হবে না।

এখন দেখবো এটা কিভাবে করা যায়। এটি আসলে খুব সহজে একটা এ্যারে এর মাধ্যমে করে ফেলা যায়। এ্যারেতে আমরা প্রতি নাম্বার এর রিটার্ন করা রেজাল্ট স্টোর করে রাখবো।

আমরা একটা এ্যারে ডিক্লেয়ার করবো ও সেখানে সব ইন্ডেক্সে -১ করে রাখবো।

তারপর আমরা যখন রিকারশিভ কল করবো তখন রিটার্ন হওয়ার সময় ভ্যালু গুলো সেই এ্যারেতে সেইভ করে রেখে দিব।

এরপর যখন ৫ থেকে ৩ কল হতে যাবে তখন সেই এ্যারেতে চেক করে দেখবে যে ভ্যালু -১ আছে কিনা। এখন এখানে দেখবে যে এ্যারে এর ৩ তম ইন্ডেক্সে এখন ২ ক্যালকুলেট করা আছে। তখন সেই ভ্যালু রিটার্ন করে দিবে আর পুনরায় কল করবে না। তারপর সেই ভ্যালু আর ৪ এর ভ্যালু যোগ হয়ে ৫ এর ভ্যালু সেট হবে।

// Some code
ll dp[N];
ll fibo(ll n)
{
    //base case n<=1
    if (n == 0 || n == 1)
    {
        return n;
    }
    //Checking if the value is precalculated or not
    if (dp[n] != -1)
    {
        return dp[n];
    }
    //If not then calculating it and saving it in the array
    ll ans = fibo(n - 1) + fibo(n - 2);
    dp[n] = ans;
    return ans;
}

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

// Some code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e6 + 5;
ll dp[N];
ll fibo(ll n)
{
    if (n == 0 || n == 1)
    {
        return n;
    }
    if (dp[n] != -1)
    {
        return dp[n];
    }
    ll ans = fibo(n - 1) + fibo(n - 2);
    dp[n] = ans;
    return ans;
}
int main()
{
    ll n;
    cin >> n;
    memset(dp, -1, sizeof(dp));
    cout << fibo(n) << endl;
    return 0;
}