ডায়নামিক প্রোগ্রামিং পরিচিতি#

ডায়নামিক প্রোগ্রামিং-এর মূল কথা হলো একই গণনা বারবার না করা। অনেক সময়, ডায়নামিক প্রোগ্রামিং সমস্যাগুলো স্বাভাবিকভাবেই রিকার্সন দিয়ে সমাধানযোগ্য। এই ক্ষেত্রে, সবচেয়ে সহজ উপায় হলো প্রথমে রিকার্সিভ সমাধানটা লেখা, তারপর রিপিটেড স্টেটগুলো একটা লুকআপ টেবিলে সংরক্ষণ করা। এই প্রক্রিয়াটাকে মেমোয়াইজেশন (memoization) সহ টপ-ডাউন ডায়নামিক প্রোগ্রামিং বলা হয়। এটা “মেমোয়াইজেশন” (যেন আমরা একটা মেমো প্যাডে লিখছি), “মেমোরাইজেশন” নয়।

এই প্রক্রিয়ার সবচেয়ে মৌলিক ও ক্লাসিক উদাহরণগুলোর একটা হলো ফিবোনাচ্চি সিকোয়েন্স (Fibonacci sequence)। এর রিকার্সিভ সূত্র হলো $f(n) = f(n-1) + f(n-2)$ যেখানে $n \ge 2$ এবং $f(0)=0$ ও $f(1)=1$। C++-এ এটা এভাবে প্রকাশ করা হবে:

int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return f(n - 1) + f(n - 2);
}

এই রিকার্সিভ ফাংশনের রানটাইম এক্সপোনেনশিয়াল — প্রায় $O(2^n)$, কারণ একটা ফাংশন কল ($f(n)$) থেকে প্রায় একই আকারের ২টা ফাংশন কল ($f(n-1)$ এবং $f(n-2)$) তৈরি হয়।

মেমোয়াইজেশন দিয়ে ফিবোনাচ্চি দ্রুততর করা (ডায়নামিক প্রোগ্রামিং)#

আমাদের বর্তমান রিকার্সিভ ফাংশনটা এক্সপোনেনশিয়াল সময়ে ফিবোনাচ্চি সমাধান করে। তারমানে, সমস্যাটা অত্যন্ত কঠিন হয়ে ওঠার আগে আমরা কেবল ছোট ইনপুট মান নিয়ে কাজ করতে পারি। উদাহরণস্বরূপ, $f(29)$-এর ফলে ১০ লক্ষেরও বেশি ফাংশন কল হয়!

গতি বাড়ানোর জন্য, আমরা লক্ষ্য করি যে সাবপ্রবলেমের সংখ্যা মাত্র $O(n)$। মানে, $f(n)$ বের করতে আমাদের শুধু $f(n-1),f(n-2), \dots ,f(0)$ জানা দরকার। তাই, এই সাবপ্রবলেমগুলো বারবার বের না করে আমরা সেগুলো একবার সমাধান করব এবং ফলাফল একটা লুকআপ টেবিলে সংরক্ষণ করব। পরবর্তী কলগুলো এই লুকআপ টেবিল ব্যবহার করবে এবং সাথে সাথে ফলাফল ফেরত দেবে, ফলে এক্সপোনেনশিয়াল কাজ দূর হবে!

প্রতিটা রিকার্সিভ কল একটা লুকআপ টেবিলে পরীক্ষা করবে মানটা আগে বের করা হয়েছে কিনা। এটা $O(1)$ সময়ে হয়। যদি আমরা আগেই এটা বের করে থাকি, তাহলে ফলাফল ফেরত দেওয়া হয়; নাহলে, আমরা ফাংশনটা স্বাভাবিকভাবে হিসাব করি। সামগ্রিক রানটাইম হলো $O(n)$। আমাদের আগের এক্সপোনেনশিয়াল সময়ের অ্যালগরিদমের তুলনায় এটা একটা বিশাল উন্নতি!

const int MAXN = 100;
bool found[MAXN];
int memo[MAXN];

int f(int n) {
    if (found[n]) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    found[n] = true;
    return memo[n] = f(n - 1) + f(n - 2);
}

আমাদের নতুন মেমোয়াইজড রিকার্সিভ ফাংশনে, $f(29)$, যেটা আগে ১০ লক্ষেরও বেশি কল তৈরি করত, এখন মাত্র ৫৭টা কল তৈরি করে — প্রায় ২০,০০০ গুণ কম ফাংশন কল! মজার বিষয় হলো, এখন আমরা ডেটা টাইপ দ্বারা সীমাবদ্ধ। $f(46)$ হলো শেষ ফিবোনাচ্চি সংখ্যা যেটা signed ৩২-বিট ইন্টিজারে ধারণ করা যায়।

সাধারণত, আমরা স্টেটগুলো অ্যারেতে (array) সংরক্ষণ করার চেষ্টা করি, কারণ লুকআপ সময় $O(1)$ এবং ওভারহেড সর্বনিম্ন। তবে, আরও সাধারণভাবে, আমরা যেকোনো উপায়ে স্টেট সংরক্ষণ করতে পারি। অন্যান্য উদাহরণের মধ্যে রয়েছে বাইনারি সার্চ ট্রি (binary search tree, C++-এ map) অথবা হ্যাশ টেবিল (hash table, C++-এ unordered_map)।

এর একটি উদাহরণ হতে পারে:

unordered_map<int, int> memo;
int f(int n) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    return memo[n] = f(n - 1) + f(n - 2);
}

অথবা অনুরূপভাবে:

map<int, int> memo;
int f(int n) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    return memo[n] = f(n - 1) + f(n - 2);
}

এই দুটোই প্রায় সবসময় একটা সাধারণ মেমোয়াইজড রিকার্সিভ ফাংশনের জন্য অ্যারে-ভিত্তিক ভার্সনের চেয়ে ধীর হবে। স্টেট সংরক্ষণের এই বিকল্প পদ্ধতিগুলো মূলত তখনই কাজে আসে যখন স্টেট স্পেসের অংশ হিসেবে ভেক্টর বা স্ট্রিং সংরক্ষণ করতে হয়।

মেমোয়াইজড রিকার্সিভ ফাংশনের রানটাইম বিশ্লেষণের সহজ পদ্ধতি হলো:

$$\text{work per subproblem} * \text{number of subproblems}$$

বাইনারি সার্চ ট্রি (C++-এ map) ব্যবহার করে স্টেট সংরক্ষণ করলে টেকনিক্যালি $O(n \log n)$ সময় লাগবে, কারণ প্রতিটা লুকআপ ও ইনসার্শনে $O(\log n)$ কাজ হয় এবং $O(n)$টা ইউনিক সাবপ্রবলেম থাকায় মোট সময় $O(n \log n)$।

এই পদ্ধতিকে টপ-ডাউন (top-down) বলা হয়, কারণ আমরা একটা কোয়েরি মান দিয়ে ফাংশন কল করি এবং গণনা উপর থেকে (কোয়েরি করা মান) শুরু হয়ে নিচের দিকে (রিকার্সনের বেস কেস) যায়, এবং পথে মেমোয়াইজেশনের মাধ্যমে শর্টকাট নেয়।

বটম-আপ ডায়নামিক প্রোগ্রামিং#

এখন পর্যন্ত তুমি শুধু মেমোয়াইজেশন সহ টপ-ডাউন ডায়নামিক প্রোগ্রামিং দেখেছ। তবে, আমরা বটম-আপ (bottom-up) ডায়নামিক প্রোগ্রামিং দিয়েও সমস্যা সমাধান করতে পারি। বটম-আপ হলো টপ-ডাউনের ঠিক বিপরীত — তুমি নিচ থেকে (রিকার্সনের বেস কেস) শুরু করো এবং ক্রমশ আরও বেশি মানে প্রসারিত করো।

ফিবোনাচ্চি সংখ্যার জন্য বটম-আপ পদ্ধতি তৈরি করতে, আমরা একটা অ্যারেতে বেস কেসগুলো ইনিশিয়ালাইজ করি। তারপর, কেবল অ্যারেতে রিকার্সিভ ডেফিনিশনটা ব্যবহার করি:

const int MAXN = 100;
int fib[MAXN];

int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) fib[i] = fib[i - 1] + fib[i - 2];

    return fib[n];
}

অবশ্যই, এভাবে লেখা দুটো কারণে কিছুটা অযৌক্তিক: প্রথমত, আমরা যদি ফাংশনটা একাধিকবার কল করি তাহলে একই কাজ বারবার হয়। দ্বিতীয়ত, বর্তমান উপাদানটা বের করতে আমাদের শুধু আগের দুটো মান দরকার। তাই, আমরা মেমোরি $O(n)$ থেকে $O(1)$-এ কমিয়ে আনতে পারি।

ফিবোনাচ্চির একটা বটম-আপ ডায়নামিক প্রোগ্রামিং সমাধানের উদাহরণ যেটা $O(1)$ মেমোরি ব্যবহার করে:

const int MAX_SAVE = 3;
int fib[MAX_SAVE];

int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i % MAX_SAVE] = fib[(i - 1) % MAX_SAVE] + fib[(i - 2) % MAX_SAVE];

    return fib[n % MAX_SAVE];
}

লক্ষ্য করো: আমরা কনস্ট্যান্টটা MAXN থেকে MAX_SAVE-এ পরিবর্তন করেছি। কারণ আমাদের মোট যতগুলো উপাদানে অ্যাক্সেস দরকার সেটা মাত্র ৩টা। এটা আর ইনপুটের আকারের সাথে বাড়ে না এবং ডেফিনিশন অনুসারে $O(1)$ মেমোরি। এছাড়া, আমরা একটা সাধারণ কৌশল (মডুলো অপারেটর ব্যবহার করে) প্রয়োগ করে শুধু প্রয়োজনীয় মানগুলো সংরক্ষণ করি।

এটাই মূল কথা। এটাই ডায়নামিক প্রোগ্রামিং-এর মূল ভিত্তি: আগে যে কাজ করেছ সেটা আবার করো না।

ডায়নামিক প্রোগ্রামিং-এ আরও দক্ষ হওয়ার একটা কৌশল হলো কিছু ক্লাসিক উদাহরণ স্টাডি করা।

ক্লাসিক ডায়নামিক প্রোগ্রামিং সমস্যা#

নাম	বিবরণ/উদাহরণ
০-১ ন্যাপস্যাক	$N$টি আইটেম দেওয়া আছে যাদের ওজন $w_i$, মান $v_i$ এবং সর্বোচ্চ ওজন $W$। $k$ আকারের ($1 \le k \le N$) প্রতিটি সাবসেটের জন্য সর্বোচ্চ $\sum_{i=1}^{k} v_i$ কত, যেখানে $\sum_{i=1}^{k} w_i \le W$ নিশ্চিত করতে হবে?
সাবসেট সাম	$N$টা পূর্ণসংখ্যা এবং $T$ দেওয়া আছে। দেওয়া সেটের এমন কোনো সাবসেট আছে কিনা বের করো যার উপাদানগুলোর যোগফল $T$ হয়।
লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স (LIS)	$N$টা পূর্ণসংখ্যা বিশিষ্ট একটা অ্যারে দেওয়া আছে। অ্যারেতে LIS বের করো, মানে এমন একটা সাবসিকোয়েন্স যেখানে প্রতিটা উপাদান আগেরটার চেয়ে বড়।
২-মাত্রিক অ্যারেতে পথ গণনা	$N$ এবং $M$ দেওয়া আছে। $(1,1)$ থেকে $(N, M)$ পর্যন্ত সব সম্ভাব্য ভিন্ন পথ গণনা করো, যেখানে প্রতিটা ধাপ $(i,j)$ থেকে $(i+1,j)$ অথবা $(i,j+1)$-এ যায়।
লংগেস্ট কমন সাবসিকোয়েন্স	স্ট্রিং $s$ এবং $t$ দেওয়া আছে। দীর্ঘতম স্ট্রিং-এর দৈর্ঘ্য বের করো যেটা $s$ এবং $t$ উভয়ের সাবসিকোয়েন্স।
ডিরেক্টেড অ্যাসাইক্লিক গ্রাফে (DAG) দীর্ঘতম পথ	ডিরেক্টেড অ্যাসাইক্লিক গ্রাফে (DAG) দীর্ঘতম পথ নির্ণয়।
লংগেস্ট প্যালিনড্রমিক সাবসিকোয়েন্স	একটা দেওয়া স্ট্রিং-এর লংগেস্ট প্যালিনড্রমিক সাবসিকোয়েন্স (LPS) নির্ণয়।
রড কাটিং	$n$ একক দৈর্ঘ্যের একটা রড দেওয়া আছে। একটা পূর্ণসংখ্যা অ্যারে cuts দেওয়া আছে যেখানে cuts[i] বোঝায় কোথায় কাটতে হবে। একটা কাটের খরচ হলো কাটা রডের দৈর্ঘ্য। কাটগুলোর সর্বনিম্ন মোট খরচ কত?
এডিট ডিস্ট্যান্স	দুটো স্ট্রিং-এর মধ্যে এডিট ডিস্ট্যান্স (edit distance) হলো একটা স্ট্রিংকে অন্যটাতে রূপান্তর করতে প্রয়োজনীয় সর্বনিম্ন অপারেশন সংখ্যা। অপারেশনগুলো হলো [“Add”, “Remove”, “Replace”]।