Bappy's Blog

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে একটি ইন্টিজার অ্যারে দেয়া থাকবে যেখানে দুটি সংখ্যা ব্যাতিত বাকি সংখ্যাগুলো দুইবার করে থাকবে এবং ঐ দুটি সংখ্যা একবার করে থাকবে। বলতে হবে সংখ্যা দুটি কি কি? আমাদেরকে এই কাজ O(n) Time Complexity এবং O(1) Memory Complexity তে করতে হবে।  Solution: আমরা জানি, একই সংখ্যাকে জোড় সংখ্যক বার এক্সর করলে ফলাফল শূন্য হয়। ধরে নেই, অ্যারেতে একবার করে থাকা সংখ্যা দুটি x এবং y । তাহলে, z = a[1] ^ a[2] ^ ... ^ a[n] = x ^ y এখন, যেহেতু সংখ্যা দুটি একবার করে আছে তার মানে x এবং y দুটি ভিন্ন সংখ্যা! সুতরাং, তাদের এক্সর করলে অন্তত এমন একটি বিট থাকবে যে বিট সংখ্যাদ্বয়ের মধ্যে তফাৎ গড়ে দিবে! তাই, z = x ^ y হলে z এর সর্বডানের কোন বিট টি অন আছে সেটি দেখবো। মনে করি, z = x^y এর সর্বডানের অন বিট টি হলো kth Bit এখন, তাহলে অ্যারের যেসব সংখ্যার kth Bit অন তাদের এক্সর করলে সেটি হবে দুটির সংখ্যার একটি সংখ্যা x । কারণ , x ভিন্ন অন্য কোন সংখ্যার kth Bit ON থাকলেও সেটি দুইবার থাকবে যেকারণে সেখানে শুধু x ই থেকে যাবে।  এখন অপর সংখ্যা y কি হবে? z = x^y

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে একটি ইন্টিজার অ্যারে দেয়া থাকবে যেখানে একটি সংখ্যা বাদে বাকি সংখ্যাগুলো এক্সেক্টলি দুইবার করে থাকবে এবং ঐ সংখ্যাটি একবার থাকবে।  আমাদেরকে একবার থাকা সংখ্যাটি বের করতে হবে। O(n) Time Complexity এবং O(1) Memory Complexity তে কাজটি করতে হবে।  Solution: বিটওয়াইজ অপারেশনগুলো নিয়ে মোটামুটি ধারণা আছে এমন যেকেউ প্রথম দেখায় প্রব্লেমটি সলভ করতে পারবে। আমরা জানি, 1 XOR 1 = 0 0 XOR 0 = 0 1 XOR 0 = 1 0 XOR 1 = 1 বিটওয়াইজ এক্সর এর ফর্মুলা গুলো জানা থাকলে দেখবে যে একই সংখ্যা দুইবার এক্সর করলে ফলাফল শূন্য! আসলে, দুইবার নয়। যেকোন জোড় সংখ্যকবার একটি সংখ্যাকে এক্সর করলে ফলাফল শূন্য। যেহেতু, অ্যারে তে ১টি সংখ্যা বাদে বাকিসব সংখ্যা ই দুইবার করে আছে সেহেতু অ্যারের সবগুলো সংখ্যা এক্সর করলে যে সংখ্যাটি পাওয়া যায় সেটিই আমাদের কাঙ্ক্ষিত সংখ্যা। 

এই পর্ব পড়ার আগে  Range GCD & Point Update  পর্বটি পড়া আবশ্যক।   Problem: এই প্রব্লেমে আমাদের একটি অ্যারে দেয়া থাকবে n সাইজের এবং q সংখ্যক কুয়েরী এন্সার করতে হবে। দুই ধরনের কুয়েরী থাকবে।  1 L R                অ্যারের L থেকে R Index পর্যন্ত সংখ্যাগুলোর GCD বের করতে হবে। 2 L R x              অ্যারের L থেকে R ইনডেক্স পর্যন্ত সংখ্যাগুলোর ভ্যালু x বাড়াতে হবে।  Solution: আমরা জানি,  GCD(a , b) = GCD(a , b-a) = GCD(a-b , b) = GCD(abs(a-b) , a) = GCD(abs(a-b) , b) GCD(a , b , c) = GCD(a , GCD(b , c)) উপরোক্ত দুটি সমীকরণ থেকে লিখতে পারি, GCD(a , b , c) = GCD(a , GCD(b-a , c-b)) অর্থাৎ, GCD(a[l] , a[l+1] , a[l+2] , ... , a[r]) = GCD(a[l] , a[l+1]-a[l] , a[l+2]-a[l+1] , ... , a[r]-a[r-1]) এখন, এই প্রব্লেম এ আমরা দুটি সেগমেন্ট ট্রি ব্যাবহার করবো।  ১) ১ম সেগমেন্ট ট্রি তে আমরা মূল অ্যারের বর্তমান অবস্থা কি সেটার হিসাব রাখবো। অর্থাৎ, মূল অ্যারের কোন ইনডেক্সের ভ্যালু বর্তমানে কত সেটা জানবো। এবং রেঞ্জ আপডেট করবো।  ২) এরপর, আমরা মূল অ্যারের জন্য একটি ডিফারেন্স অ্যারে তৈরী করবো। যেখানে,     dif[i] =

 Problem: এই প্রব্লেমে আমাদের একটি অ্যারে দেয়া থাকবে n সাইজের এবং q সংখ্যক কুয়েরী এন্সার করতে হবে। দুই ধরনের কুয়েরী থাকবে।  1 L R           অ্যারের L to R index পর্যন্ত সংখ্যাগুলোর GCD বের করতে হবে।  2 pos x         অ্যারের pos তম পজিশনের ভ্যালু x বাড়িয়ে দাও।  Solution: সেগমেন্ট ট্রি এর রেঞ্জ কুয়েরী এবং পয়েন্ট আপডেট সম্পর্কে ধারনা থাকলেই এই প্রব্লেম সলভ করা সম্ভব। তাই বিস্তারিত আলোচনা না করে সরাসরি কোডে যাচ্ছিঃ  Suggested problem Happy Coding 

শুরুতেই বলে রাখি এই এপিক টপিক আমি শিখেছি এই  CF Blog  থেকে।  SOS DP: SOS(Sum Over Subset) মূলত একটি সংখ্যার সবগুলো সাবমাস্ক এফিসিয়েন্টলি ইটারেট করে।  সাবমাস্ক কি?           একটি সংখ্যা x এর একটি সাবমাস্ক হবে y যদি x & y = y হয়।            সহজ ভাষায় বললে, একটি সংখ্যার kth বিট যদি 0 হয় তবে তার সাবমাস্ক এর kth বিট অবশ্যই 0               হবে এবং যদি সংখ্যাটির kth বিট 1 হয় তবে তার সাবমাস্কের kth বিট 0 অথবা 1 যেকোন কিছু হতে           পারে।                    তাহলে, একটি সংখ্যার On bit যদি k টা হয় তবে তার সাবমাস্ক হতে পারে 2^k টা। এখন ধরে নেই, S(mask) = {x : x & mask = x} অর্থাৎ, S(mask) হচ্ছে mask সংখ্যাটির সাবমাস্কের সেট।  S(mask , i) হচ্ছে মাস্কের এমন সব সাবমাস্কের এর সেট যাদের 0th to ith পজিশনের বিটগুলো শুধু পরিবর্তন হতে পারবে।  এখন, S এবং সাবমাস্ক এর সংজ্ঞা থেকে আমরা লিখতে পারিঃ S(mask , i) = S(mask , i-1)                                                                     IF  ith bit is OFF S(mask , i) = S(mask , i-1) U S(mask XOR (1<<i) , i-1)          I

 Problem Description  here Problem: এই প্রব্লেমে তোমাকে n সংখ্যক থালা দেয়া হবে। প্রতিটি থালা তে ১টি, ২টি অথবা ৩টি করে খাবার থাকবে। যতোক্ষণ না পর্যন্ত সবগুলো থালার সবগুলো খাবার শেষ না হয় ততোক্ষণ পর্যন্ত তুমি একটি ছক্কার গুটি নিক্ষেপ করবে যেখানে 1 to n পর্যন্ত সংখ্যাগুলো দেখানোর সম্ভাব্যতা সমান। ছক্কা নিক্ষেপে যদি i সংখ্যাটি উঠে তাহলে তুমি i তম থালার একটি খাবার খাবে। যদি i তম থালায় কোন খাবার না থাকে তাহলে কিছুই করা লাগবে না। তোমাকে বলতে হবে সবগুলো থালার সব খাবার শেষ করতে এক্সপেক্টেড কত সময় লাগবে?  এই প্রব্লেমটি সলভ করতে  Expected Value  সম্পর্কে জানা জরুরী।  Recursive Solution: Next Episode  

 Problem Description  Click here এটি ইন্টারভাল ডিপির আরো একটি প্রব্লেম।  Problem: একটি সারিতে তোমাকে n টি Slime দেয়া আছে। এবং তাদের সাইজের অ্যারে a[n] দেয়া আছে। এখন তোমাকে সবগুলো Slime কম্বাইন করে একটি বড় Slime তৈরী করতে হবে। দুটি Slime শুধুমাত্র তখনই কম্বাইন করা যাবে যখন তারা পাশাপাশি অবস্থিত হবে। এবং দুটি Slime এর কস্ট X এবং Y হলে তাদেরকে কম্বাইন করার কস্ট হবে X+Y। বলতে হবে, সর্বনিম্ন কত কস্টে সবগুলো Slime কম্বাইন করা যায়?  Recursive Solution: ১) আমরা প্রব্লেমটিকে একটু উল্টোভাবে চিন্তা করি। অর্থাৎ, ধরে নেই শুরুতে সবগুলো Slime কম্বাইন করা আছে। আমাকে বের করতে হবে সবগুলো Slime আলাদা করার সর্বনিম্ন কস্ট।  একটি Slime কে দুইভাগে ভাগ করার কস্ট হবে ঐ Slime এর মোট সাইজ। ২) স্টেট হবে দুটি। স্টেট-১ঃ lft          (Starting position of this combined slime) স্টেট-২ঃ rgt         (Ending position of this combined slime) dp[lft][rgt] মানে হচ্ছে, ara[lft...rgt] সবগুলো Slime কম্বাইনড অবস্থায় আছে। তাদেরকে আলাদা করার কস্টই dp[lft][rgt] ৩) শুরুতে যদি আমরা ara র প্রিপিক্স সাম বের করে রাখি তাহলে ara[lf

 Problem Description  here Problem: এই প্রব্লেমে দুইজন প্লেয়ার একটি গেম খেলবে। যেটা হবেঃ একটি পাথরের স্তূপ আছে যেখানে K সংখ্যক পাথর আছে। এবং n টি সংখ্যার একটি অ্যারে দেয়া আছে। প্রথম চাল দিবে ১ম জন, ২য় চাল ২য় জন, ৩য় চাল ১ম জন, ৪র্থ চাল ২জন, এভাবে খেলা চলতে থাকবে। প্রতি চালে একজন প্লেয়ার অ্যারে থেকে যেকোন একটি সংখ্যা নিবে এবং এক্সেক্টলি ততোগুলো পাথর স্তূপ থেকে ফেলে দিবে। যদি কোন প্লেয়ার তার চালে কোন পাথরই না ফেলতে পারে তবে সে হারবে।  বলতে হবে, দুইজন প্লেয়ারই অপ্টিমালি খেললে কে জিতবে?  Recursive Solution:  ১) এই প্রব্লেমে আমাদের স্টেট নিতে হবে দুটি।     স্টেট-১ঃ বর্তমানে স্তুপে কয়টি পাথর অবশিষ্ট আছে।     স্টেট-২ঃ এখন কোন প্লেয়ার চাল দিবে।  ২) সল্যুশনে আমরা প্রথম প্লেয়ার কে ০তম এবং ২য় প্লেয়ার কে ১তম প্লেয়ার হিসেবে বিবেচনা করেছি। ৩) বেস কেসে পৌঁছানো মানে এখন আর চাল দেয়া সম্ভব নয়। অর্থাৎ, বেস কেসে যদি ১ম প্লেয়ার পৌঁছায় তার মানে ২য় প্লেয়ার উইনার আর যদি ২য় প্লেয়ার পৌঁছায় তার মানে ১ম প্লেয়ার উইনার।  ৪) বেস কেস ভিন্ন, যেহেতু দুইজন প্লেয়ার অপ্টিমালি খেলবে সেহেতু এখন যদি ১ম প্লেয়ার এর চাল হয় তবে ১

 Problem Description  here Problem: এটি মূলত ইন্টারভাল ডিপির একটি প্রব্লেম। এই প্রব্লেমে দুইজন প্লেয়ার একটি গেম খেলবে। গেমটা হচ্ছে, n সাইজের একটি অ্যারে দেয়া আছে। প্রতি চালে একজন প্লেয়ার অ্যারের সর্ববামের অথবা সর্বডানের ভ্যালুটা নিবে এবং সেটি অ্যারে থেকে বাদ দিবে। ১ম প্লেয়ার এর মোট স্কোর X এবং ২য় প্লেয়ার এর মোট স্কোর Y হলে, ১ম প্লেয়ার চাইবে X-Y ম্যাক্সিমাইজ করতে এবং ২য় প্লেয়ার চাইবে X-Y মিনিমাইজ করতে। ২জন প্লেয়ার অপ্টিমালি খেলবে।  উল্লেখ্য যে, ১ম চাল ১ম প্লেয়ার এর, ২য় চাল ২য় প্লেয়ার, ৩য় চাল ১ম প্লেয়ার, ৪র্থ চাল ২য় প্লেয়ার এভাবে চলবে।  Recursive Solution: ১) এই প্রব্লেমে প্রথম প্লেয়ার এর টার্গেট হচ্ছে X-Y ম্যাক্সিমাইজ করা এবং ২য় প্লেয়ার এর টার্গেট হচ্ছে X-Y মিনিমাইজ করা। ভালোভাবে লক্ষ্য করলে দেখবে যে, এর মানে হচ্ছে উভয় প্লেয়ার  চায় তার নিজের স্কোর যতোটা সম্ভব বাড়াতে। ২) কিন্তু, আমরা একই সাথে উভয় প্লেয়ার এর স্কোর নিয়ে কাজ করতে পারি না। তাহলে উপায়? আরেকটি ব্যাপার কি লক্ষ্য করেছো? অ্যারের যেসব ভ্যালু ১ম প্লেয়ার নিবে না সেগুলো অবশ্যই ২য় প্লেয়ার নিবে!  তাহলে, ব্যাপারটি কি দাঁড়ালো?  আমরা যদি

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে n সাইজের একটি অ্যারে দেয়া হবে। K সংখ্যক ক্যান্ডি n সংখ্যক বাচ্চাদের মধ্যে এমনভাবে ভাগ করে দিতে হবে যাতে ith বাচ্চার প্রাপ্ত ক্যান্ডির সংখ্যা 0 থেকে a[i] এর মধ্যে হয়। এবং কোন ক্যান্ডি বাকি থাকা যাবে না। বলতে হবে, কতভাবে ক্যান্ডিগুলো বিতরণ করা যাবে? Solution: ইতোপূর্বে লিখা ডিপি অপ্টিমাইজেশনের পর্বগুলো পড়ে থাকলে এই প্রব্লেমটি সলভ করা অনেকটা সহজ যে কারণে এই প্রব্লেম নিয়ে আর বিস্তারিত আলোচনা করছি না। সল্যুশন দেখা যাকঃ Next Episode Happy Coding

 Problem Description  here Problem: এই প্রব্লেমটি সাধারণ একটি ন্যাপসেক প্রব্লেম যা দিয়েই মূলত আমরা ডিপি শেখা শুরু করি। যেকারণে, এই প্রব্লেমের বিস্তারিত আলোচনা করবো না।  Recursive Solution: Iterative Solution: Next episode Happy Coding

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে দুটি স্ট্রিং দেয়া থাকবে। আমাদেরকে স্ট্রিং দুটির Longest Common Subsequence প্রিন্ট করতে হবে। যদি LCS এর লেন্থ বের করতে বলতো তাহলে শুধু ডিপি করা পর্যন্তই সীমাবদ্ধ থাকতো। কিন্তু, এখানে ডিপি সল্যুশন প্রিন্ট করতে হবে।  Recursive Solution: ১) এই প্রব্লেমের জন্য আমাদের দুটি স্টেট রাখতে হবে। একটি হচ্ছে আমি বর্তমানে প্রথম স্ট্রিং এর কোন পজিশনে আছি এবং অন্যটি হচ্ছে আমি এখন দ্বিতীয় স্ট্রিং এর কোন পজিশনে আছি।  ২) যদি s1[pos1] == s2[pos2] হয় তবে এই ম্যাচটি কাউন্ট করে দুটি স্টেট এর ভ্যালু ১ বাড়িয়ে পরবর্তী ট্রাঞ্জিশনে যাওয়া ই বেটার। ৩) অন্যথায়, একবার pos1 কে বাড়িয়ে দেখবো এবং আবার pos2 কে বাড়িয়ে দেখবো। এবং LCS ম্যাক্সিমাইজ করবো।  এবার সল্যুশন প্রিন্ট কিভাবে করবো?  যেকোন রিকার্সিভ ডিপি প্রব্লেমের সল্যুশন প্রিন্ট এর ধাপগুলোঃ ১) হুবহু ডিপি ফাংশনটি কপি করে আরেকটি ফাংশন বানাবো যার রিটার্ণ টাইপ হবে void. ২) বেসকেসে শুধু return লিখবো। ৩) dp[state-1][state-2]...[state-k] != -1 হলে ক্যালকুলেটেড ভ্যালুটি রিটার্ণ করো এই লাইনদুটি বাদ দিবো।  ৪) এখন, যেহেতু

 Problem Description  here Problem: এই প্রব্লেমে আমাদের মূলত একটি DAG দেয়া থাকবে। Longest Directed Path এর লেন্থ বের করতে হবে।  Solution: এই প্রব্লেমে আমরা মূলত প্রতিটি নোড থেকে DFS ছেড়ে দেখবো যে কত Depth এ যাওয়া সম্ভব। এভাবে প্রতিটি নোডের জন্য প্রাপ্ত ভ্যালু নিয়ে এন্সার ম্যাক্সিমাইজ করবো।  Next Episode Happy Coding 

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে n * m সাইজের একটি 2D গ্রীড দেয়া থাকবে যার কিছু সেল ফাঁকা এবং কিছু সেল ব্লকড। ফাঁকা সেলগুলো দিয়েই শুধু হাঁটা সম্ভব। তোমাকে বের করতে হবে (1,1) সেল থেকে (n,m) সেলে যাওয়ার মোট কয়টি পাথ আছে যদি তুমি শুধুমাত্র নিচের এবং ডানের সেলে মুভ করতে পারো।  Recursive Solution: ১) এই প্রব্লেমে স্টেট হবে দুটি। একটি আমি বর্তমানে গ্রীডের কত নং সারিতে আছি এবং অন্যটি কত নং কলামে আছি। ২) এরপর আমি বর্তমান সেল থেকে নিচের সেলে মুভ দিবো যদি সেটি ফাঁকা এবং গ্রীডের ভিতরে অবস্থিত হয় এবং বর্তমান সেল এর ডানের সেলে মুভ দিবো যদি সেটি ফাঁকা এবং গ্রীডের ভিতরে অবস্থিত হয়। ৩) যখন আমরা (n,m) সেলে পৌছাবো সেটি হবে বেস কেস। এবং বেস কেসে ১ রিটার্ন করবো।  Iterative Solution: গত পর্বগুলো সব পড়ে আসলে এতোক্ষণে তুমি নিশ্চয়ই ইটারেটিভ ডিপি ভালোই বুঝো। যেকারণে বিস্তারিত ব্যাখ্যায় গেলাম না 😛 Next Episode Happy Coding 

 Problem Description  here Problem : n সংখ্যক কয়েন দেয়া আছে। যেখানে ith কয়েন টস করলে হেড উঠার সম্ভাব্যতা P[i] এবং টেল উঠার সম্ভাব্যতা 1 - P[i] সবগুলো কয়েন টস করলে টেল এর থেকে হেড বেশি পাওয়ার সম্ভাব্যতা কত সেটি বের করতে হবে।  Recursive Solution: ১) এই প্রব্লেমে আমাদের স্টেট নিতে হবে ২টি। একটি হচ্ছে, এখন কত তম কয়েন টস করবো অর্থাৎ পজিশন এবং অন্যটি হলো এখন পর্যন্ত কয়টি কয়েন এ হেড পেয়েছি। ২) বেস কেসে এ চেক দিবো যে টেল এর থেকে বেশি সংখ্যক হেড পেয়েছি কি না। যদি পাই তাহলে ১ রিটার্ন করবো। অন্যথায় ০ রিটার্ন করবো। ০ রিটার্ন করার অর্থ হচ্ছে ডিপি ট্রি এর রুট নোড থেকে বর্তমান নোড পর্যন্ত যে পাথ সেটি ভ্যালিড কোন পাথ না। ৩) প্রতিটি সাব-প্রব্লেম এ হেড উঠলে টেল অপেক্ষা বেশি হেড পাওয়ার সম্ভাব্যতা কত বের করবো এবং টেল উঠলে টেল অপেক্ষা হেড বেশি পাওয়ার সম্ভাব্যতা কত বের করবো। এবং দুটি ফলাফল যোগ করবো।  ভালোভাবে লক্ষ্য করলে বুঝবে যে এখানে আমরা টেল অপেক্ষা হেড বেশি পাওয়ার যে সম্ভাব্যতা সেটি রিটার্ন করছি সর্বদা। dp[i][j] বলতে বোঝানো হচ্ছে 1st to ith পজিশন পর্যন্ত j সংখ্যক হেড পেলে টেল অপেক্ষা বেশি হেড পাওয়ার সম্

Problem Description  here Problem: এই প্রব্লেমটির সঙ্গে আগের প্রব্লেমের পার্থক্য হচ্ছে, আগের প্রব্লেমে একঘর অথবা দুইঘর জাম্প দেয়া যেতো কিন্তু এই প্রব্লেমে সর্বোচ্চ k ঘর জাম্প দিতে পারবো।  Recursive Solution: ১) এই প্রব্লেমেও আমাদের স্টেট থাকবে পজিশন।  ২) এরপর প্রতি পজিশন থেকে ১ঘর, ২ঘর,..., k ঘর জাম্প করে দেখবো কত খরচ হয়। এদের মধ্যে মিনিমাম খরচ টি ই রিটার্ন করবো।  বুঝতেই পারতেছো প্রতিবার সর্বোচ্চ k ঘর জাম্প দেয়ার জন্য k সাইজের একটি ইনার লুপ ব্যাবহার করতে হবে। Iterative Solution: এই প্রব্লেমের ইটারেটিভ সল্যুশন প্রায় আগের প্রব্লেমের সল্যুশন এর মতোই। শুধুমাত্র একটি অতিরিক্ত ইনার লুপ ব্যাবহার করতে হবে k ঘর পর্যন্ত জাম্প করার জন্য।  Next episode Happy Coding

 Problem Description  here Problem: এই প্রব্লেমে বলা হয়েছে, তুমি n দিনের ছুটিতে যাবা। ছুটির প্রতিটি দিন তুমি প্রব্লেমে উল্লেখিত ৩টি কাজের যেকোন একটি করতে পারবে। ১ম কাজ করলে তুমি a[i], ২য় কাজ করলে তুমি b[i], ৩য় কাজ করলে c[i] পয়েন্ট পাবা। এখন তোমাকে বের করতে হবে সর্বোচ্চ কত পয়েন্ট পাওয়া সম্ভব যদি তুমি পরপর দুইদিন একই কাজ না কর।  Recursive Solution: ১) এই প্রব্লেমে আমাদের দুটি স্টেট লাগবে। একটি হচ্ছে বর্তমানে আমি কোন পজিশনে আছি এবং অন্যটি হচ্ছে ঠিক আগের পজিশনে আমি উল্লেখিত ৩টি কাজের মধ্যে কোনটি করে আসছি। ২) এরপর, প্রতি পজিশনের জন্য আমি ৩টি কাজের মধ্যে সেসব কাজের জন্য মোট পয়েন্ট বের করবো যে কাজ ঠিক আগের পজিশনে করা হয় নি।  এবং সেখান থেকে মোট পয়েন্ট এর পরিমাণ ম্যাক্সিমাইজ করবো।  Iterative Solution: ১) একটু ভালোভাবে লক্ষ্য করলে দেখবে যে ১ম পজিশনে আমরা যেকোন একটি কাজ করতে পারি। শর্ত চলে আসে ২য় পজিশন থেকে। ২য় পজিশনে আমরা সেই কাজটি করতে পারি না যা অলরেডি ১ম পজিশনে করে এসেছি। ২) তার মানে ২য় থেকে পরবর্তী পজিশন গুলোতে আমি ১ম কাজ করলে ১ম কাজের জন্য প্রাপ্ত পয়েন্ট এর সাথে যোগ হবে তার ঠিক আগের পজিশনে

কিছু কথাঃ DP Series এ আমি মূলত  At Coder Educational DP  কন্টেস্টের প্রব্লেমগুলো নিয়ে আলোচনা করবো এবং সেই সাথে ডিপি সল্যুশন প্রিন্ট, ডিপি অপটিমাইজেশনসহ আরো কিছু বিষয় নিয়ে আলোচনা করবো।  এই সিরিজ টি পড়া শুরু করার আগে সবার ব্যাসিক ডিপি সম্পর্কে ধারণা থাকা আবশ্যক।  এজন্য  শাফায়েতের ব্লগ  থেকে ডাইনামিক প্রোগ্রামিং এর সবগুলো পর্ব পড়ে নেয়ার জন্য অনুরোধ করছি।  Problem Description  here Problem: প্রব্লেমটিতে বলা হয়েছে, আমাদেরকে n টি পাথর দেয়া থাকবে। এবং প্রতিটি পাথরের উচ্চতা দেয়া থাকবে।  একটি ব্যাঙ শুরুতে ১নম্বর পাথরে আছে। ব্যাঙ টি একঘর অথবা দুইঘর জাম্প করতে পারে। অর্থাৎ, i তম পাথর থেকে i+1 or i+2 তম পাথরে যেতে পারে। ith থেকে jth পাথরে যেতে তাকে দুইটি স্টোনের উচ্চতার পার্থক্যের সমান টাকা খরচ করতে হয়।  বের করতে হবে n তম পাথরে পৌঁছাতে তাকে সর্বনিম্ন কত খরচ করতে হবে?  Recursive Solution: ১) এই প্রব্লেমের জন্য আমাদের কয়টি স্টেট লাগবে? ভালোভাবে লক্ষ্য করলে বুঝবে শুধুমাত্র পজিশন ই স্টেট হিসেবে রাখা যথেষ্ট।  ২) এরপর, প্রতি পজিশন থেকে আমি একবার একঘর জাম্প করে দেখবো কত খরচ হয়। তারপর, যদি সম্ভব হয় দুইঘর