ডাইনামিক প্রোগ্রামিং (Dynamic Programming in C)

ডাইনামিক প্রোগ্রামিং (Dynamic Programming in C)

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

ডাইনামিক প্রোগ্রামিং এর দুটি মৌলিক উপাদান:

1. অভারল্যাপিং সাবপ্রোবলেম (Overlapping Subproblems): সমস্যা ছোট ছোট সাবপ্রোবলেমে ভেঙে পড়তে পারে এবং এসব সাবপ্রোবলেম একাধিক বার সমাধান হতে পারে। ডাইনামিক প্রোগ্রামিং এ সাবপ্রোবলেমগুলোর ফলাফল সংরক্ষণ করে পুনরায় একই সাবপ্রোবলেম সমাধান থেকে বিরত থাকে।
2. অপটিমাল সাবস্ট্রাকচার (Optimal Substructure): একটি সমস্যা এমনভাবে সমাধান করা যায় যে তার সমাধান ছোট ছোট সাবপ্রোবলেমের সমাধানগুলোর উপরে নির্ভর করে।

ডাইনামিক প্রোগ্রামিং এর প্রকারভেদ:

1. টপ-ডাউন (Top-Down Approach): এতে রিকার্সন ব্যবহার করে সমস্যার সমাধান করা হয় এবং উপ-সমস্যার ফলাফলগুলো সংরক্ষণের জন্য মেমোইজেশন (Memoization) ব্যবহার করা হয়।
2. বটম-আপ (Bottom-Up Approach): এতে ইটারেটিভ পদ্ধতিতে সমাধান করা হয় এবং উপ-সমস্যাগুলোর সমাধান শুরু থেকে শেষ পর্যন্ত তৈরি করা হয়।

ডাইনামিক প্রোগ্রামিং এর উদাহরণ: ফিবোনাচ্চি সিরিজ (Fibonacci Series)

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

Top-Down Approach (Memoization) for Fibonacci Sequence in C:

#include <stdio.h>

// Memoization array to store the Fibonacci numbers
int memo[1000];

// Function to calculate Fibonacci number using top-down approach
int fibonacci(int n) {
    if (n <= 1)
        return n;

    // Check if result is already computed
    if (memo[n] != -1)
        return memo[n];

    // Calculate and store the result in the memo array
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    // Initialize the memo array with -1 to signify uncomputed values
    for (int i = 0; i < 1000; i++) {
        memo[i] = -1;
    }

    int n;
    printf("Enter a number: ");
    scanf("%d", &n);

    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));

    return 0;
}

ব্যাখ্যা:

1. memo[] array ব্যবহার করে আগে হিসাব করা ফিবোনাচ্চি মানগুলো সংরক্ষণ করা হয়।
2. যখন কোনো মান পূর্বে গণনা করা থাকে, তখন সেটা পুনরায় গণনা না করে সরাসরি ব্যবহৃত হয়, যা সময় কমাতে সাহায্য করে।
3. এটি একটি টপ-ডাউন অ্যাপ্রোচ (Recursive + Memoization)।

Bottom-Up Approach (Tabulation) for Fibonacci Sequence in C:

#include <stdio.h>

// Function to calculate Fibonacci number using bottom-up approach
int fibonacci(int n) {
    int fib[n + 1];

    // Initialize the first two numbers in the Fibonacci series
    fib[0] = 0;
    fib[1] = 1;

    // Compute all Fibonacci numbers up to n
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);

    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));

    return 0;
}

ব্যাখ্যা:

1. বটম-আপ অ্যাপ্রোচ ব্যবহার করা হয়েছে, যেখানে প্রথম থেকেই শুরু করে ধাপে ধাপে Fibonacci সিরিজের মান গণনা করা হয়।
2. এখানে কোনো রিকার্সন নেই এবং একে একে সব মান গণনা করা হচ্ছে, যা O(n) সময়ে কাজ করে।

ডাইনামিক প্রোগ্রামিংয়ের অন্যান্য উদাহরণ:

1. এন-থ টাইপ সুম (Knapsack Problem):
   • একটি অনুরূপ সমস্যা যেখানে একটি ব্যাগের মধ্যে নির্দিষ্ট ওজনের আইটেমগুলি ভরার জন্য সর্বাধিক মান বের করা হয়।
   • এটি টপ-ডাউন বা বটম-আপ পদ্ধতিতে সমাধান করা যায়।
2. লংস্ট কমন সাবসিকোয়েন্স (Longest Common Subsequence - LCS):
   • দুটি স্ট্রিং এর মধ্যে সবচেয়ে বড় সাধারণ সাবসিকোয়েন্স খুঁজে বের করা।
3. Shortest Path Problems (Dijkstra’s Algorithm):
   • ডাইনামিক প্রোগ্রামিং ব্যবহৃত হয় নেটওয়ার্ক রুটিং সমস্যা সমাধানে, যেমন ডাইকস্ট্রার অ্যালগরিদম।

ডাইনামিক প্রোগ্রামিংয়ের সুবিধা:

1. অপটিমাল সাবস্ট্রাকচার: সমস্যার সমাধান ছোট ছোট উপ-সমস্যার সমাধান থেকে তৈরি হয়, যা সহজেই ডাইনামিক প্রোগ্রামিংয়ের মাধ্যমে সমাধান করা যায়।
2. অভারল্যাপিং সাবপ্রোবলেম: একই উপ-সমস্যা একাধিক বার সমাধান হওয়া থেকে বিরত থাকে এবং সেগুলি সংরক্ষিত হয়।
3. কাজের গতি বাড়ানো: রিকার্সনের বদলে ইটারেটিভ বা টেবুলেশন ব্যবহার করে কাজের গতি বাড়ানো যায়।

সারসংক্ষেপ:

ডাইনামিক প্রোগ্রামিং একটি শক্তিশালী কৌশল যা ছোট ছোট উপ-সমস্যার সমাধান সংরক্ষণ করে মূল সমস্যার সমাধান দ্রুত করে। এটি বিশেষভাবে ব্যবহারী হয় অপটিমাইজেশন সমস্যা সমাধানে এবং বেশিরভাগ ক্ষেত্রে Memoization (Top-Down) এবং Tabulation (Bottom-Up) পদ্ধতি ব্যবহার করা হয়। Fibonacci সিরিজের মতো সমস্যা সমাধান করা এর একটি সাধারণ উদাহরণ।

Dynamic Programming এর ধারণা এবং প্রয়োজনীয়তা

Dynamic Programming (DP) একটি শক্তিশালী কৌশল, যা সমস্যা সমাধানের জন্য ছোট ছোট উপ-সমস্যাগুলির সমাধান সংরক্ষণ করে বড় সমস্যা সমাধান করতে ব্যবহৃত হয়। এটি সাধারণত এমন সমস্যাগুলির জন্য ব্যবহৃত হয় যেখানে উপসমস্যাগুলির পুনরাবৃত্তি (overlapping subproblems) থাকে এবং অপটিমাল সাবস্ট্রাকচার (optimal substructure) অনুসরণ করে। DP মূলত দুটি মূল ধারণার উপর ভিত্তি করে কাজ করে: মেমোইজেশন (Memoization) এবং **টেবিল-ভিত্তিক (Tabulation)**।

Dynamic Programming এর মৌলিক ধারণা:

1. উপসমস্যাগুলির পুনরাবৃত্তি (Overlapping Subproblems):
   • সমস্যার সমাধান করতে গেলে, অনেক সময় একই উপসমস্যার সমাধান একাধিকবার প্রয়োজন হয়। Dynamic Programming এমন পরিস্থিতিতে ব্যবহৃত হয়, যেখানে একই উপসমস্যাগুলির সমাধান বারবার করা হয়। এর ফলে, একই উপসমস্যার সমাধান পুনরায় না করে সেগুলিকে সংরক্ষণ করে রাখা হয়।
   • উদাহরণস্বরূপ, Fibonacci সংখ্যা বের করার ক্ষেত্রে, Fibonacci(n) এবং Fibonacci(n-1) বারবার গণনা হতে পারে, যা পুনরাবৃত্তি উপসমস্যা তৈরি করে।
2. অপটিমাল সাবস্ট্রাকচার (Optimal Substructure):
   • একটি সমস্যা যদি একটি বা একাধিক ছোট উপসমস্যা দ্বারা বিভক্ত হয়ে থাকে এবং সেই উপসমস্যাগুলির সমাধানগুলি একত্রিত করে মূল সমস্যার সমাধান পাওয়া যায়, তবে তাকে অপটিমাল সাবস্ট্রাকচার বলা হয়।
   • উদাহরণস্বরূপ, একটি সর্বনিম্ন খরচ পথ খুঁজে বের করার জন্য, ছোট ছোট অংশের সর্বনিম্ন খরচ পথ খুঁজে বের করে মূল পথের সর্বনিম্ন খরচ পাওয়া যায়।

Dynamic Programming এর প্রয়োজনীয়তা:

Dynamic Programming বিশেষভাবে প্রয়োজন হয় যখন:

1. পুনরাবৃত্তি উপসমস্যা (Overlapping Subproblems):

   • যখন একটি বড় সমস্যার সমাধান ছোট ছোট উপসমস্যার সমাধান দিয়ে পুনরাবৃত্তি করা যায়।
   • একাধিক বার একই উপসমস্যার সমাধান প্রয়োজন হয়, তখন DP ব্যবহৃত হয়। এতে একই কাজ পুনরায় করতে না হয়ে পূর্ববর্তী সমাধানগুলো সংরক্ষণ করা হয়।

   উদাহরণ:

   • Fibonacci সিরিজ গণনা করা, যেখানে Fibonacci(n) সমাধান করতে Fibonacci(n-1) এবং Fibonacci(n-2) বারবার গাণনা করা হয়।
2. অপটিমাল সাবস্ট্রাকচার (Optimal Substructure):
   • সমস্যা যদি ছোট ছোট অংশে বিভক্ত হয়ে সমাধানযোগ্য হয় এবং এগুলোর সমাধান একত্রিত করে মূল সমস্যার সমাধান করা যায়।
   • যেমন, কমপক্ষে খরচে রাস্তা খোঁজা, যেখানে ছোট রাস্তা (subpaths) খুঁজে বের করে পুরো রাস্তার খরচ নির্ধারণ করা যায়।
3. সমস্যার আংশিক সমাধান সংরক্ষণ (Storing Partial Solutions):
   • Dynamic Programming দ্বারা আংশিক সমাধানগুলো সংরক্ষণ করে রাখা হয়, যাতে পরে প্রয়োজন হলে সেই সমাধানগুলো পুনরায় ব্যবহার করা যায়। এটি গাণিতিক কার্যকারিতা বৃদ্ধি করে।
4. সময়সীমা (Time Complexity):
   • যখন সমস্যা সমাধানে একটি ধাপে ধাপে কাজ করতে হয় এবং পুনরাবৃত্তি বা কম্বিনেশন অপারেশনগুলোকে অনুক্রমিকভাবে (recursive) সমাধান করা সম্ভব নয়, তখন DP এর সাহায্যে একটি অপটিমাল সময় জটিলতায় (optimal time complexity) সমাধান পাওয়া যায়।
   • উদাহরণ: Fibonacci সংখ্যা নির্ধারণে নৈমিত্তিক পুনরাবৃত্তি ছাড়া একাধিক উপসমস্যা পুনরাবৃত্তি হলে DP অ্যালগরিদম ব্যবহার করে সময়ের সাশ্রয় করা যায়।

Dynamic Programming এর ব্যবহার:

1. Fibonacci Sequence:
   • Fibonacci সংখ্যার জন্য DP ব্যবহার করা হয়, যেখানে Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)। পুনরাবৃত্তি এড়িয়ে DP দ্বারা দ্রুত সমাধান করা হয়।
2. Longest Common Subsequence (LCS):
   • দুটি স্ট্রিংয়ের মধ্যে সর্বোচ্চ সাধারণ উপসিকোয়েন্স বের করার সমস্যা। DP ব্যবহার করে ছোট ছোট অংশের সমাধানগুলো সংরক্ষণ করে মূল সমস্যা সমাধান করা হয়।
3. Knapsack Problem:
   • কোনো নির্দিষ্ট ওজনের মধ্যে সর্বোচ্চ লাভ অর্জন করার সমস্যা। এটি একটি ক্লাসিক DP সমস্যা যেখানে প্রতিটি আইটেমের জন্য বিভিন্ন ওজন এবং লাভ এর সমন্বয় বের করা হয়।
4. Shortest Path Algorithms:
   • Dijkstra অ্যালগরিদম বা Floyd-Warshall অ্যালগরিদমের মতো গ্রাফ সম্পর্কিত সমস্যাগুলোতে DP ব্যবহার করা হয় সর্বনিম্ন খরচের পথ খোঁজার জন্য।
5. Matrix Chain Multiplication:
   • যখন একাধিক ম্যাট্রিক্সের গুণফল বের করা হয়, তখন DP ব্যবহার করে খরচ বা সংখ্যার গুণফল সঠিকভাবে নির্ধারণ করা যায়।

Dynamic Programming এর পদ্ধতিসমূহ:

1. Memoization (Top-Down Approach):
   • এটি রিকার্সিভ পদ্ধতির উপর ভিত্তি করে কাজ করে। এখানে উপসমস্যাগুলোর সমাধান মেমোরি বা ক্যাশে মেমরিতে সংরক্ষিত থাকে, যাতে পুনরাবৃত্তি না হয়।
2. Tabulation (Bottom-Up Approach):
   • এটি একটি ইটারেটিভ পদ্ধতি, যেখানে ছোট থেকে বড় উপসমস্যাগুলি সমাধান করা হয় এবং পরবর্তীতে সেগুলোর সমন্বয়ে মূল সমস্যার সমাধান পাওয়া যায়। এখানে মেমরি টেবিল ব্যবহার করা হয়।

Dynamic Programming এর উদাহরণ:

Fibonacci Sequence (Memoization):

#include <stdio.h>

#define MAX 100

int memo[MAX];

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

int main() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;  // Initialize memoization table
    }
    
    int n = 10;  // Fibonacci number for position 10
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
    
    return 0;
}

সারসংক্ষেপ:

Dynamic Programming (DP) একটি শক্তিশালী টেকনিক যা পুনরাবৃত্তি উপসমস্যাগুলির সমাধান সংরক্ষণ করে বড় সমস্যা সমাধান করতে সাহায্য করে। এটি অপটিমাল সাবস্ট্রাকচার এবং পুনরাবৃত্তি উপসমস্যার সমাধান সংরক্ষণের মাধ্যমে সময় সাশ্রয় করে এবং সমস্যা সমাধানে দক্ষতা বাড়ায়। DP এর প্রধান প্রয়োগ ক্ষেত্রগুলো হলো Fibonacci সিরিজ, Knapsack সমস্যা, Shortest Path, LCS এবং Matrix Chain Multiplication।

Memoization এবং Tabulation এর মাধ্যমে সমস্যা সমাধান

Memoization এবং Tabulation দুটি ডাইনামিক প্রোগ্রামিং (Dynamic Programming, DP) কৌশল যা সমস্যার সমাধানে পুনরাবৃত্তি থেকে পরিহার করতে এবং একাধিক সমাধান পুনরায় না করতে সহায়তা করে। এই দুটি পদ্ধতির মধ্যে পার্থক্য আছে, তবে লক্ষ্য একটাই: উপ-সমস্যাগুলির সমাধান সঞ্চয় (store) করা, যাতে একই সমস্যার পুনরাবৃত্তি এড়ানো যায় এবং সময় সাশ্রয়ী হয়।

Memoization

Memoization একটি টপ-ডাউন (Top-Down) পদ্ধতি, যেখানে সমস্যার সমাধান গণনা করার সময় উপ-সমস্যাগুলি একবার সমাধান করা হয় এবং পরে সেগুলিকে একটি কেশে (cache) সংরক্ষণ করা হয়, যাতে পরবর্তী সময়ে যদি আবার সেই উপ-সমস্যাগুলি আসে, তাহলে পুনরায় গণনা না করে কেবল কেশ থেকে ফলাফল নেওয়া যায়।

Memoization এর ধাপ:

1. প্রাথমিকভাবে একটি রিকার্সিভ ফাংশন তৈরি করা হয় যা সমস্যার সমাধান করে।
2. উপ-সমস্যাগুলির ফলাফল কেশে সংরক্ষণ করা হয় (একটি অ্যারে বা হ্যাশ টেবিল ব্যবহার করা হয়)।
3. যদি কোন উপ-সমস্যার ফলাফল কেশে থাকে, তবে তা ফেরত দেওয়া হয়, অন্যথায় নতুনভাবে গণনা করা হয় এবং কেশে সংরক্ষণ করা হয়।

Memoization এর উদাহরণ: Fibonacci সিরিজ:

#include <stdio.h>

#define MAX 100

// Memoization টেবিল
int memo[MAX];

// ফিবোনাচ্চি সিরিজের রিকার্সিভ ফাংশন
int fibonacci(int n) {
    // বেস কেস
    if (n <= 1) return n;

    // যদি কেশে ফলাফল থাকে, তবে তা ফেরত দাও
    if (memo[n] != -1) return memo[n];

    // রিকার্সিভ কল এবং ফলাফল কেশে সংরক্ষণ
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

int main() {
    // Memoization টেবিলের সব মান -1 দিয়ে শুরু
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }

    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));

    return 0;
}

Memoization এর সুবিধা:

• সময় সাশ্রয়ী: উপ-সমস্যার পুনরাবৃত্তি এড়িয়ে কাজ দ্রুত হয়।
• টপ-ডাউন: রিকার্সিভ কোড ব্যবহার করা হয় যা সাধারণত সহজভাবে বোঝা যায়।

Memoization এর অসুবিধা:

• স্ট্যাক ওভারফ্লো: রিকার্সন গভীর হলে স্ট্যাক সমস্যা হতে পারে, যেমন অত্যধিক রিকার্সিভ কল।

Tabulation

Tabulation একটি বটম-আপ (Bottom-Up) পদ্ধতি, যেখানে উপ-সমস্যাগুলির সমাধান টেবিলের মাধ্যমে তৈরি করা হয় এবং শেষ পর্যন্ত মূল সমস্যার সমাধান বের করা হয়। এটি একটি ইটারেটিভ পদ্ধতি, যেখানে আগের উপ-সমস্যাগুলির ফলাফলগুলি টেবিলে রাখা হয় এবং প্রতিটি উপ-সমস্যার সমাধান পূর্ববর্তী সমাধানগুলির ওপর নির্ভর করে গণনা করা হয়।

Tabulation এর ধাপ:

1. একটি টেবিল তৈরি করা হয় (অর্থাৎ একটি অ্যারে বা 2D টেবিল) যা উপ-সমস্যাগুলির সমাধান ধারণ করবে।
2. ছোট উপ-সমস্যাগুলি থেকে শুরু করে বড় সমস্যার সমাধান ইটারেটিভভাবে গণনা করা হয়।
3. ফলাফল টেবিলের সর্বশেষ উপাদানে পাওয়া যায়।

Tabulation এর উদাহরণ: Fibonacci সিরিজ:

#include <stdio.h>

#define MAX 100

// ট্যাবুলেশন ফাংশন
int fibonacci(int n) {
    // টেবিল তৈরি
    int dp[MAX];
    
    // বেস কেস
    dp[0] = 0;
    dp[1] = 1;

    // ট্যাবুলেশন: পূর্ববর্তী ফলাফল ব্যবহার করে পরবর্তী ফলাফল হিসাব করা
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

int main() {
    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));

    return 0;
}

Tabulation এর সুবিধা:

• কম স্পেস: রিকার্সন ব্যবহার না করার কারণে স্ট্যাক সমস্যা হয় না।
• টপ-ডাউন পদ্ধতির চেয়ে দ্রুত: ইটারেটিভ পদ্ধতি ট্যাবুলেশন ব্যবহার করলে অনেক সময় দ্রুত সমাধান পাওয়া যায়।

Tabulation এর অসুবিধা:

• জটিলতা: কখনও কখনও কোড বুঝতে বা লেখা কঠিন হতে পারে।
• স্মৃতি প্রয়োজন: পুরো টেবিল সংরক্ষণ করতে অনেক মেমরি লাগতে পারে।

Memoization বনাম Tabulation

সারসংক্ষেপ

• Memoization এবং Tabulation উভয়ই ডাইনামিক প্রোগ্রামিং কৌশল, তবে তারা আলাদা পদ্ধতিতে কাজ করে। Memoization টপ-ডাউন পদ্ধতি, যেখানে সমস্যার সমাধান রিকার্সিভভাবে করা হয় এবং উপ-সমস্যাগুলির ফলাফল সংরক্ষণ করা হয়। Tabulation একটি বটম-আপ পদ্ধতি, যেখানে উপ-সমস্যাগুলি ইটারেটিভভাবে সমাধান করা হয়।
• Memoization যেখানে সহজ ও দ্রুত প্রোগ্রামিং প্রদান করে, Tabulation সেখানে অনেক বেশি কার্যকরী হতে পারে যখন বড় পরিমাণ ডেটা বা উপ-সমস্যা থাকলে।
• উভয় পদ্ধতিরই নিজস্ব সুবিধা এবং সীমাবদ্ধতা আছে, এবং সমস্যা অনুযায়ী উপযুক্ত পদ্ধতি নির্বাচন করা উচিত।

Fibonacci Series এবং Knapsack Problem এর Dynamic Programming ইমপ্লিমেন্টেশন

1. Fibonacci Series (Dynamic Programming)

ফিবোনাচ্চি সিরিজ হল একটি সিকোয়েন্স যেখানে পরবর্তী সংখ্যাটি আগের দুটি সংখ্যার যোগফল। এই সিরিজটি সাধারণত এইভাবে শুরু হয়:
\[ F(0) = 0, F(1) = 1 \]
আর এরপরের সবগুলো সংখ্যা হচ্ছে:
\[ F(n) = F(n-1) + F(n-2) \]

যদিও এটি রিকার্সিভভাবে সোজা সোজা সমাধান করা যায়, তবে তা কার্যকরী নয়, কারণ এটি অনেক পুনরাবৃত্তি করে। এখানে Dynamic Programming ব্যবহার করে কার্যকরভাবে এটি সমাধান করা যায়।

Fibonacci Series - Dynamic Programming ইমপ্লিমেন্টেশন:

#include <stdio.h>

// Fibonacci using Dynamic Programming (Tabulation)
long long fibonacci(int n) {
    long long dp[n+1];
    
    // Base cases
    dp[0] = 0;
    dp[1] = 1;

    // Fill the dp array iteratively
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

int main() {
    int n;
    printf("Enter the number to find Fibonacci: ");
    scanf("%d", &n);
    
    printf("Fibonacci number at position %d is: %lld\n", n, fibonacci(n));
    
    return 0;
}

Output Example:

Enter the number to find Fibonacci: 10
Fibonacci number at position 10 is: 55

Fibonacci Dynamic Programming-এর সুবিধা:

• Time Complexity: O(n), কারণ প্রতিটি উপাদান একবারের জন্য হিসাব করা হয়।
• Space Complexity: O(n), কারণ আমরা একটি অ্যারে ব্যবহার করছি সবার মান রাখার জন্য।

2. Knapsack Problem (0/1 Knapsack) - Dynamic Programming

Knapsack Problem একটি ক্লাসিক্যাল অপটিমাইজেশন সমস্যা যেখানে আমাদের একটি সীমিত ধারণক্ষমতার ব্যাগ (Knapsack) আছে এবং কিছু আইটেম দেয়া আছে, যেগুলোর নির্দিষ্ট মান (value) এবং ওজন (weight) রয়েছে। আমাদের উদ্দেশ্য হল এমন আইটেমগুলি নির্বাচন করা যাতে তাদের মোট ওজন ব্যাগের ধারণক্ষমতার মধ্যে থাকে এবং তাদের মোট মান সর্বাধিক হয়।

Problem Definition (0/1 Knapsack):

• আমাদের কাছে Nটি আইটেম, প্রতিটির একটি ওজন \( w[i] \) এবং একটি মান \( v[i] \)।
• আমাদের কাছে একটি ব্যাগ, যার ধারণক্ষমতা \( W \)।
• আমাদের কাজ হল এমন আইটেমগুলো নির্বাচন করা যাতে ব্যাগের ওজন \( W \)-এর মধ্যে থাকে এবং তাদের মান সর্বাধিক হয়।

Knapsack Problem - Dynamic Programming ইমপ্লিমেন্টেশন:

#include <stdio.h>

// Knapsack Problem using Dynamic Programming
int knapsack(int W, int w[], int v[], int n) {
    int dp[n+1][W+1]; // DP table to store solutions to subproblems

    // Fill the DP table
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0; // Base case: no items or capacity is 0
            } else if (w[i-1] <= j) {
                // If the item can be included in the current capacity
                dp[i][j] = (v[i-1] + dp[i-1][j-w[i-1]]) > dp[i-1][j] ?
                            (v[i-1] + dp[i-1][j-w[i-1]]) : dp[i-1][j];
            } else {
                // If the item can't be included
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // The last cell contains the maximum value
    return dp[n][W];
}

int main() {
    int n, W;

    // Input number of items and knapsack capacity
    printf("Enter number of items: ");
    scanf("%d", &n);
    printf("Enter capacity of knapsack: ");
    scanf("%d", &W);

    int weights[n], values[n];

    // Input weights and values of items
    printf("Enter weights of items: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }

    printf("Enter values of items: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &values[i]);
    }

    // Call knapsack function and display the result
    printf("Maximum value in knapsack = %d\n", knapsack(W, weights, values, n));
    
    return 0;
}

Output Example:

Enter number of items: 4
Enter capacity of knapsack: 5
Enter weights of items: 1 2 3 8
Enter values of items: 20 5 10 40
Maximum value in knapsack = 60

Knapsack Dynamic Programming-এর সুবিধা:

• Time Complexity: O(n * W), যেখানে n হল আইটেমের সংখ্যা এবং W হল ব্যাগের ধারণক্ষমতা।
• Space Complexity: O(n * W), কারণ ডিপি টেবিলের সাইজ হলো \( n \times W \)।

সারসংক্ষেপ:

1. Fibonacci Series:
   • Dynamic Programming ব্যবহার করে Fibonacci সিরিজের মান দ্রুত ও কার্যকরভাবে বের করা যায়। এতে মেমরি ব্যবহার সঠিকভাবে নিয়ন্ত্রণ করা হয় এবং সময় জটিলতা O(n) এ কমিয়ে আনা হয়।
2. Knapsack Problem:
   • 0/1 Knapsack সমস্যা সমাধান করতে Dynamic Programming ব্যবহার করা হয়, যাতে সীমিত ধারণক্ষমতা সহ সর্বাধিক মান পাওয়া যায়। এর সময় জটিলতা O(n * W) এবং স্পেস জটিলতা O(n * W), যেখানে n হল আইটেমের সংখ্যা এবং W হল ব্যাগের ধারণক্ষমতা।

Divide and Conquer বনাম Dynamic Programming

Divide and Conquer (D&C) এবং Dynamic Programming (DP) দুটি গুরুত্বপূর্ণ অ্যালগরিদমিক ধারণা, যা অনেক ধরনের কম্পিউটেশনাল সমস্যা সমাধানে ব্যবহৃত হয়। যদিও উভয়ের উদ্দেশ্য সাধারণভাবে সমস্যাগুলোকে ছোট উপ-সমস্যায় বিভক্ত করা, তাদের কাজ করার পদ্ধতি এবং প্রয়োগ ভিন্ন। নিচে তাদের পার্থক্য এবং মূল ধারণা তুলে ধরা হলো।

Divide and Conquer (D&C)

Divide and Conquer একটি সমস্যা সমাধানের কৌশল যেখানে সমস্যা তিনটি প্রধান ধাপে বিভক্ত করা হয়:

1. Divide: সমস্যাটি ছোট ছোট উপ-সমস্যায় ভাগ করা হয়।
2. Conquer: প্রতিটি উপ-সমস্যা সমাধান করা হয় (এটি সাধারণত রিকার্সিভভাবে করা হয়)।
3. Combine: উপ-সমস্যাগুলোর সমাধান একত্রিত করে মূল সমস্যার সমাধান বের করা হয়।

D&C অ্যালগরিদমগুলি সাধারণত রিকার্সিভ হয় এবং এটি অস্তিত্বের ওপর ভিত্তি করে কাজ করে, যেখানে উপ-সমস্যাগুলি একে অপরের সাথে নির্ভরশীল হতে পারে না।

D&C উদাহরণ:

• Merge Sort: একটি অ্যারের উপাদানগুলি দুইটি ভাগে ভাগ করা হয় এবং প্রতিটি অংশকে আলাদাভাবে সাজানো হয়। তারপর সাজানো অংশগুলি একত্রিত করা হয়।
• Quick Sort: একটি পিভট নির্বাচন করে অ্যারের উপাদানগুলোকে দুটি ভাগে ভাগ করা হয় এবং প্রতিটি ভাগে আলাদাভাবে সাজানো হয়।
• Binary Search: একটি লিস্টের মধ্যে একটি উপাদান খোঁজা হয়, যেখানে প্রতিবার লিস্টের অর্ধেক অংশ বাদ দেওয়া হয়।

D&C-এর বৈশিষ্ট্য:

• অস্তিত্ব নির্ভর সমস্যা সমাধান: প্রতিটি উপ-সমস্যা একে অপরের থেকে স্বাধীনভাবে সমাধান করা হয়।
• রিকার্সিভ প্রকৃতি: এই ধরনের অ্যালগরিদমে উপ-সমস্যাগুলি ছোট ছোট ভাগে বিভক্ত করা হয়, এবং সাধারণত এটি একটি রিকার্সিভ ফাংশন ব্যবহৃত হয়।

D&C-এর সময় জটিলতা:

• সাধারণত O(log n) বা O(n log n) সময়ে কাজ করে, যেমন Merge Sort বা Quick Sort।

Dynamic Programming (DP)

Dynamic Programming একটি অ্যালগরিদমিক কৌশল যা সমস্যাগুলির উপ-সমস্যাগুলির সমাধান একাধিক বার ব্যবহার করে। DP সাধারণত অপটিমাইজেশন সমস্যা সমাধানে ব্যবহৃত হয়, যেখানে একটি সমস্যা অনেক ছোট উপ-সমস্যায় ভেঙে এবং তাদের মধ্যে কোনো একটি উপ-সমস্যার ফলাফল একাধিকবার ব্যবহৃত হতে পারে। DP এ, মেমোইজেশন বা টেবিলিং ব্যবহৃত হয়, যার মাধ্যমে একবার সমাধান করা উপ-সমস্যাগুলির ফলাফল সংরক্ষণ করা হয় এবং পরে তা আবার ব্যবহার করা হয়, যাতে পুনরাবৃত্তি হওয়ার সম্ভাবনা থাকে না।

DP উদাহরণ:

• Fibonacci Sequence: ফিবোনাচি সিরিজের যেকোনো উপাদান খুঁজতে DP ব্যবহার করা যেতে পারে, যেখানে পূর্ববর্তী ফলাফলগুলিকে সংরক্ষণ করে নতুন উপাদান হিসাব করা হয়।
• Knapsack Problem: একটি ব্যাগে বিভিন্ন পণ্য রাখা হলে, ব্যাগের সর্বোচ্চ মান বের করা যেতে পারে যাতে প্রতিটি পণ্য অন্তর্ভুক্ত বা বাদ দেওয়া যায়।
• Shortest Path (Bellman-Ford, Floyd-Warshall): বিভিন্ন নোডের মধ্যে সবচেয়ে ছোট পথ খোঁজা।

DP-এর বৈশিষ্ট্য:

• অপটিমাইজেশন সমস্যা: DP সাধারণত এমন সমস্যাগুলিতে ব্যবহৃত হয় যেখানে suboptimal solutions থেকে optimal solution বের করতে হয়।
• Overlap Subproblems: সমস্যা সমাধান করার সময় অনেক উপ-সমস্যার সমাধান একাধিকবার আসতে পারে।
• Optimal Substructure: যদি একটি সমস্যা এমনভাবে বিভক্ত করা যায় যাতে তার সঠিক সমাধান তার উপ-সমস্যাগুলির সঠিক সমাধান থেকে নির্ধারিত হয়, তবে তা DP তে সমাধানযোগ্য।

DP-এর সময় জটিলতা:

• O(n^2), O(n^3) অথবা O(nm), যেখানে n এবং m বিভিন্ন সমস্যা অনুযায়ী ভিন্ন হতে পারে।

Divide and Conquer বনাম Dynamic Programming

সারসংক্ষেপ

• Divide and Conquer এমন একটি পদ্ধতি যেখানে একটি বড় সমস্যা ছোট ছোট উপ-সমস্যায় ভাগ করা হয় এবং প্রতিটি উপ-সমস্যা স্বাধীনভাবে সমাধান করা হয়। এটি সাধারণত রিকার্সিভ হয় এবং অস্তিত্বের ওপর নির্ভরশীল।
• Dynamic Programming একটি পদ্ধতি যেখানে উপ-সমস্যাগুলির সমাধান পুনরায় ব্যবহৃত হয়। এটি অপটিমাইজেশন সমস্যাগুলির সমাধান করার জন্য ব্যবহৃত হয় এবং সাধারণত মেমোইজেশন বা টেবিলিং ব্যবহার করা হয়।

D&C এবং DP উভয়ের উদ্দেশ্য প্রায় এক হলেও, D&C সাধারণত স্বাধীন উপ-সমস্যার সমাধান দিয়ে কাজ করে এবং DP উপ-সমস্যাগুলির পুনরাবৃত্তি সমাধান থেকে কার্যকরী ফলাফল বের করতে সাহায্য করে।