At Coder Educational DP-B | DP Series(Episode-2)

Problem Description here

Problem: এই প্রব্লেমটির সঙ্গে আগের প্রব্লেমের পার্থক্য হচ্ছে, আগের প্রব্লেমে একঘর অথবা দুইঘর জাম্প দেয়া যেতো কিন্তু এই প্রব্লেমে সর্বোচ্চ k ঘর জাম্প দিতে পারবো। 

Recursive Solution:

১) এই প্রব্লেমেও আমাদের স্টেট থাকবে পজিশন। 

২) এরপর প্রতি পজিশন থেকে ১ঘর, ২ঘর,..., k ঘর জাম্প করে দেখবো কত খরচ হয়। এদের মধ্যে মিনিমাম খরচ টি ই রিটার্ন করবো। 

বুঝতেই পারতেছো প্রতিবার সর্বোচ্চ k ঘর জাম্প দেয়ার জন্য k সাইজের একটি ইনার লুপ ব্যাবহার করতে হবে।

	#include<bits/stdc++.h>
	using namespace std;
	long long n,k,h[100005],dp[100005];
	long long fun(int pos)
	{
	if(pos == n)
	return 0;
	if(dp[pos] != -1)
	return dp[pos];
	long long opt=1e18 , ret1=1e18;
	for(int i=1 ; i<=k && i+pos<=n ; i++)
	{
	ret1=abs(h[pos]-h[pos+i]) + fun(pos+i);
	opt=min(opt,ret1);
	}
	return dp[pos]=opt;
	}
	int main()
	{
	long long i,ans;
	memset(dp , -1 , sizeof(dp));
	cin>>n>>k;
	for(i=1;i<=n;i++)
	cin>>h[i];
	ans = fun(1);
	cout<<ans<<endl;
	return 0;
	}

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

Iterative Solution:

এই প্রব্লেমের ইটারেটিভ সল্যুশন প্রায় আগের প্রব্লেমের সল্যুশন এর মতোই। শুধুমাত্র একটি অতিরিক্ত ইনার লুপ ব্যাবহার করতে হবে k ঘর পর্যন্ত জাম্প করার জন্য। 

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

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

Next episode

Happy Coding