At Coder Educational DP-A | DP Series(Episode-1)

কিছু কথাঃ DP Series এ আমি মূলত At Coder Educational DP কন্টেস্টের প্রব্লেমগুলো নিয়ে আলোচনা করবো এবং সেই সাথে ডিপি সল্যুশন প্রিন্ট, ডিপি অপটিমাইজেশনসহ আরো কিছু বিষয় নিয়ে আলোচনা করবো। 

এই সিরিজ টি পড়া শুরু করার আগে সবার ব্যাসিক ডিপি সম্পর্কে ধারণা থাকা আবশ্যক। 

এজন্য শাফায়েতের ব্লগ থেকে ডাইনামিক প্রোগ্রামিং এর সবগুলো পর্ব পড়ে নেয়ার জন্য অনুরোধ করছি। 

Problem Description here

Problem: প্রব্লেমটিতে বলা হয়েছে, আমাদেরকে n টি পাথর দেয়া থাকবে। এবং প্রতিটি পাথরের উচ্চতা দেয়া থাকবে। 

একটি ব্যাঙ শুরুতে ১নম্বর পাথরে আছে। ব্যাঙ টি একঘর অথবা দুইঘর জাম্প করতে পারে। অর্থাৎ, i তম পাথর থেকে i+1 or i+2 তম পাথরে যেতে পারে। ith থেকে jth পাথরে যেতে তাকে দুইটি স্টোনের উচ্চতার পার্থক্যের সমান টাকা খরচ করতে হয়। 

বের করতে হবে n তম পাথরে পৌঁছাতে তাকে সর্বনিম্ন কত খরচ করতে হবে? 

Recursive Solution:

১) এই প্রব্লেমের জন্য আমাদের কয়টি স্টেট লাগবে? ভালোভাবে লক্ষ্য করলে বুঝবে শুধুমাত্র পজিশন ই স্টেট হিসেবে রাখা যথেষ্ট। 

২) এরপর, প্রতি পজিশন থেকে আমি একবার একঘর জাম্প করে দেখবো কত খরচ হয়। তারপর, যদি সম্ভব হয় দুইঘর জাম্প দিয়ে দেখবো কত খরচ হয়।

৩) এরপর, মিনিমাম খরচ টি রিটার্ন করে দিবো! 

	#include<bits/stdc++.h>
	using namespace std;
	long long n,dp[100005],h[100005];
	///Here, dp[i] means minimum cost to reach nth position from ith position
	long long fun(int pos)
	{
	if(pos >= n)
	return 0;
	if(dp[pos] != -1)
	return dp[pos];
	long long ret1 = 1e18 , ret2 = 1e18;
	ret1 = abs(h[pos]-h[pos+1]) + fun(pos+1);
	if(pos < n-1)
	ret2 = abs(h[pos]-h[pos+2]) + fun(pos+2);
	return dp[pos]=min(ret1,ret2);
	}
	int main()
	{
	long long i,j,ans;
	memset(dp , -1 , sizeof(dp));
	cin>>n;
	for(i=1;i<=n;i++)
	cin>>h[i];
	ans = fun(1);
	cout<<ans<<endl;
	return 0;
	}

view raw Episode-1.1.cpp hosted with ❤ by GitHub

কোডে dp[pos] বলতে বোঝানো হয়েছে, pos তম পজিশন থেকে n তম পজিশনে সর্বনিম্ন কত খরচে যাওয়া যায়। 

Iterative Solution:

১) রিকার্সিভ ডিপির কোড দেখলে নিশ্চয়ই বুঝেছো যে, dp[i] এর ভ্যালু বের করার জন্য আমাদের dp[i+1] এবং dp[i+2] এর ভ্যালু এর দরকার হয়। মজার ব্যাপার হলো, রিকার্শন কিন্তু ভবিষ্যৎ দেখতে পারে। সে ভবিষ্যতে গিয়ে এই ভ্যালুগুলো ক্যালকুলেট করে এনে আমাদেরকে দেয়। তারপর, আমরা dp[i] এর ভ্যালু ক্যালকুলেট করতে পারি। 

২) কিন্তু, ইটারেশন এর মাধ্যমে ভবিষ্যৎ দেখা সম্ভব নয়। এই পদ্ধতি একটি আপাদমস্তক বাস্তবিক পদ্ধতি। যেকারণে, এই পদ্ধতিতে আমরা dp[n],dp[n-1],dp[n-2],...,dp[1] এই অর্ডারে ভ্যালুগুলো ক্যালকুলেট করে থাকি। 

৩) কারণ, এভাবে ক্যালকুলেট করলেই আমার পক্ষে dp[i+1],dp[i+2] এর ভ্যালু জানা সম্ভব যখন কি না আমি ith পজিশনে আছি। 

	#include<bits/stdc++.h>
	using namespace std;
	long long h[100005],dp[100005];
	///Here, dp[i] means minimum cost to reach nth position from ith position
	void Solve(int t)
	{
	long long i,j,k,n,ans;
	cin>>n;
	for(i=1 ; i<=n ; i++) cin>>h[i];
	dp[n] = 0; ///base case
	dp[n-1] = fabs(h[n] - h[n-1]);
	for(i=n-2 ; i>=1 ; i--)
	dp[i] = min(fabs(h[i]-h[i+1])+dp[i+1] , fabs(h[i]-h[i+2])+dp[i+2]);
	cout<<dp[1]<<endl;
	}
	int main()
	{
	Solve(1);
	return 0;
	}

view raw Episode-1.2.cpp hosted with ❤ by GitHub

Click here to read next episode

Happy Coding