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

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

এই প্রক্রিয়ার সবচেয়ে মৌলিক ও ক্লাসিক উদাহরণগুলোর একটি হলো ফিবোনাচ্চি সিকোয়েন্স। এর রিকার্সিভ সূত্র হলো $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 ৩২-বিট ইন্টিজারে ধারণ করা যায়।

সাধারণত, আমরা স্টেটগুলো অ্যারেতে সংরক্ষণ করার চেষ্টা করি, কারণ লুকআপ সময় $O(1)$ এবং ওভারহেড সর্বনিম্ন। তবে, আরও সাধারণভাবে, আমরা যেকোনো উপায়ে স্টেট সংরক্ষণ করতে পারি। অন্যান্য উদাহরণের মধ্যে রয়েছে বাইনারি সার্চ ট্রি (C++-এ map) অথবা হ্যাশ টেবিল (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)$।

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

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

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

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

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] নির্দেশ করে কোথায় কাটতে হবে। একটি কাটের খরচ হলো কাটা রডের দৈর্ঘ্য। কাটগুলোর সর্বনিম্ন মোট খরচ কত?
এডিট ডিস্ট্যান্স	দুটি স্ট্রিং-এর মধ্যে এডিট ডিস্ট্যান্স হলো একটি স্ট্রিংকে অন্যটিতে রূপান্তর করতে প্রয়োজনীয় সর্বনিম্ন অপারেশন সংখ্যা। অপারেশনগুলো হলো [“Add”, “Remove”, “Replace”]।