ডায়নামিক প্রোগ্রামিং বুনিয়াদি  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় ইনফোসিস ম্যাক
ডায়নামিক প্রোগ্রামিং তত্ত্ব

ডায়নামিক প্রোগ্রামিং বুনিয়াদিগুলিতে, আমরা লোপির পদ্ধতি, বিভাজন এবং বিজয় এবং পুনর্বিবেচনার থেকে ডিপি এবং এর পার্থক্যগুলি কভার করব।

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

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

ডিপির কিছু প্রাথমিক সমস্যা  

  • কুৎসিত সংখ্যা সমস্যা
  • মুদ্রা পরিবর্তন
  • ফিবোনাচি সংখ্যাগুলি
  • বেল সংখ্যা সমস্যা
  • হ্যানয়ের টাওয়ার
  • বেল সংখ্যা
  • ন্যাপস্যাক সমস্যা

ডায়নামিক প্রোগ্রামিং (ডিপি) বনাম লোভী পদ্ধতি  

ডিপিতে প্রতিটি পদক্ষেপ অনুকূল সমাধান পাওয়ার জন্য বর্তমান এবং পূর্ববর্তী সমাধানগুলি বিবেচনা করে সমাধানটি মূল্যায়ন করে। তবে, লোভী অ্যালগরিদমে আমরা কেবলমাত্র বর্তমান পরিস্থিতি বিবেচনা করে সেরা বিকল্পটি নির্বাচন করি select

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

ডায়নামিক প্রোগ্রামিং (ডিপি) বনাম ডিভাইড এবং কনকয়ের পদ্ধতি  

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

আরো দেখুন
একক সারি ব্যবহার করে একটি স্ট্যাক প্রয়োগ করুন

(মেমোয়েজেশনটি একই সমস্যার বারবার গণনা রোধ করতে সাধারণত হ্যাশ-ম্যাপে পূর্ববর্তী গণনা ফলাফলগুলি সংরক্ষণ করার কৌশল বোঝায়))

ডায়নামিক প্রোগ্রামিং (ডিপি) বনাম পুনরাবৃত্তি পদ্ধতি  

পুনরায় গণনা এড়াতে ভবিষ্যতে আবার প্রয়োজন হিসাবে ব্যবহার করার জন্য পূর্ববর্তী গণিত সমাধানগুলি ডিপি সংরক্ষণ করে। তবে পুনরাবৃত্তিতে পুনরায় গণনা হওয়ার সম্ভাবনা রয়েছে যা অপ্রয়োজনীয় কারণ এটি মান সংরক্ষণ করে না store

পুনরাবৃত্তি সমস্যাগুলির পুনরায় গণনা বেশ কয়েকবার বাড়ে তাই এরকম ক্ষেত্রে পুনরাবৃত্তির সময় জটিলতা সবসময় ডিপি সমাধানের চেয়ে বেশি।

এই নিবন্ধে, আমরা সম্পর্কে কভার ডায়নামিক প্রোগ্রামিং বুনিয়াদি। পরবর্তী নিবন্ধগুলিতে, আমরা ডিপির কয়েকটি প্রাথমিক সমস্যাগুলি কভার করব।

উল্লেখ সাক্ষাৎকার প্রশ্ন