যেখানে plain recursive function কে optimize করা হয় সেটাকে বলা যায় ডাইনামিক প্রোগ্রামিং।

যখন একটা recursive function এ same input এর জন্য বারবার ফাংশন কল করা হয় মানে already আমি একবার ফাংশন কল করে ans পেয়ে গেছি তবুও same function আমি বারবার কল করে চলেছি সেই কেস গুলোতে ডাইনামিক প্রোগ্রামিং ব্যাবহার করে সেটিকে অপটিমাইজ করা যায়।

উপায়টা হচ্ছে memoization। এটি বলতে বুঝানো হয়, যখন আমরা কোনো value র জন্য ফাংশন কল করে একটা মান পাবো সেটিকে আমরা store করে রাখবো এবং যখন ঐ ফাংশন আবার same value ধারা কল হবে তখন আমরা সেটিকে আবার calculate না করে যেখানে store করে রাখা হয়েছিল সেটা থেকে ব্যাবহার করবো।

একটা example এ আসি এবার,

সবচেয়ে আলোচিত example হচ্ছে Fibonacci series

function fib(n){
    if (n === 0 || n === 1) return 1;

    return fib(n - 1) + fib(n - 2)
}

এখানে একই কাজ বার বার করা হচ্ছে যেটা নিচের পিক টা দেখলে বুঝা যাবে। Tree এর left part এ f2 টা right part এ আবারও কল হয়েছে। যার কারণে আবারও f1 এবং f0 চলে এসেছে। যদি ট্রি টা অনেক বড় হতো তাহলে দেখা যেত একই কাজ বারবার করা হচ্ছে।

যদি এখানে value গুলো store করে রাখা হয় তাহলে right tree তে যখন যাবে তখন f2 পাওয়া মাত্রই তার কাছে value টা চলে আসবে। এক্সট্রা করে f0, f1 এর কাজ করতে হবে না। তেমনি যদি ট্রি টা অনেক বড় হতো তখন সেটা আরও গভীরভাবে পর্যবেক্ষণ করা সম্ভব হবে।

function memoizedFib(n, memo={}){
    if (memo[n]) return memo[n];
    else if (n === 0 || n === 1) return 1;

    let result = memoizedFib(n-1, memo) + memoizedFib(n-2, memo);
    memo[n] = result;

    return result;
}

এখানে n এর মান এবং একটা array নেওয়া হয়েছে store করার কাজটা করার জন্য। প্রথমেই চেক করে নেওয়া হয়েছে যে আমি যে নম্বর এর জন্য ফাংশন কল করবো সেটি আগে থেকেই calculated কিনা। যদি হয় তাহলে সেটার value return করে দিবে।

আর এভাবেই ডাইনামিক প্রোগ্রামিং কম সময়ের মধ্যেই জটিল সব কাজ করতে পারে যেটা normally করতে গেলে কম্পিউটার ঘুমিয়ে পড়ত।