At Coder Educational DP-C | DP Series(Episode-3)

 Problem Description here

Problem: এই প্রব্লেমে বলা হয়েছে, তুমি n দিনের ছুটিতে যাবা। ছুটির প্রতিটি দিন তুমি প্রব্লেমে উল্লেখিত ৩টি কাজের যেকোন একটি করতে পারবে। ১ম কাজ করলে তুমি a[i], ২য় কাজ করলে তুমি b[i], ৩য় কাজ করলে c[i] পয়েন্ট পাবা।

এখন তোমাকে বের করতে হবে সর্বোচ্চ কত পয়েন্ট পাওয়া সম্ভব যদি তুমি পরপর দুইদিন একই কাজ না কর। 

Recursive Solution:

১) এই প্রব্লেমে আমাদের দুটি স্টেট লাগবে। একটি হচ্ছে বর্তমানে আমি কোন পজিশনে আছি এবং অন্যটি হচ্ছে ঠিক আগের পজিশনে আমি উল্লেখিত ৩টি কাজের মধ্যে কোনটি করে আসছি।

২) এরপর, প্রতি পজিশনের জন্য আমি ৩টি কাজের মধ্যে সেসব কাজের জন্য মোট পয়েন্ট বের করবো যে কাজ ঠিক আগের পজিশনে করা হয় নি। 

এবং সেখান থেকে মোট পয়েন্ট এর পরিমাণ ম্যাক্সিমাইজ করবো। 

	#include<bits/stdc++.h>
	using namespace std;
	long long dp[100005][4],happy[4][100005],n;
	long long fun(int pos,int prev)
	{
	if(pos >= n+1)
	return 0;
	if(dp[pos][prev] != -1)
	return dp[pos][prev];
	long long ret1=0,opt=0;
	for(int i=1;i<=3;i++)
	{
	if(i != prev)
	{
	ret1=happy[i][pos]+fun(pos+1,i);
	opt=max(opt,ret1);
	}
	}
	return dp[pos][prev]=opt;
	}
	int main()
	{
	long long i,ans;
	memset(dp , -1 , sizeof(dp));
	scanf("%lld",&n);
	for(i=1 ; i<=n ; i++)
	{
	scanf("%lld %lld %lld",&happy[1][i],&happy[2][i],&happy[3][i]);
	}
	ans = fun(1,0);
	printf("%lld\n",ans);
	return 0;
	}

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

Iterative Solution:

১) একটু ভালোভাবে লক্ষ্য করলে দেখবে যে ১ম পজিশনে আমরা যেকোন একটি কাজ করতে পারি। শর্ত চলে আসে ২য় পজিশন থেকে। ২য় পজিশনে আমরা সেই কাজটি করতে পারি না যা অলরেডি ১ম পজিশনে করে এসেছি।

২) তার মানে ২য় থেকে পরবর্তী পজিশন গুলোতে আমি ১ম কাজ করলে ১ম কাজের জন্য প্রাপ্ত পয়েন্ট এর সাথে যোগ হবে তার ঠিক আগের পজিশনে ২য় অথবা ৩য় কাজ করলে প্রাপ্ত পয়েন্ট এর মধ্যে সর্বোচ্চ পয়েন্ট। 

এভাবে, প্রতিটি পজিশনের জন্য ৩টি কাজ ই ট্রাই করবো আমরা এবং সর্বোচ্চ ফলাফল টি রিটার্ন করবো। 

	#include<bits/stdc++.h>
	using namespace std;
	long long a[100005],b[100005],c[100005],dp[100005][4];
	int main()
	{
	long long i,j,k,n,ans;
	cin>>n;
	for(i=1 ; i<=n ; i++) cin>>a[i]>>b[i]>>c[i];
	dp[1][1] = a[1];
	dp[1][2] = b[1];
	dp[1][3] = c[1];
	for(i=2 ; i<=n ; i++){
	dp[i][1] = a[i] + max(dp[i-1][2] , dp[i-1][3]);
	dp[i][2] = b[i] + max(dp[i-1][1] , dp[i-1][3]);
	dp[i][3] = c[i] + max(dp[i-1][1] , dp[i-1][2]);
	}
	ans = max(dp[n][1] , max(dp[n][2] , dp[n][3]));
	cout<<ans<<endl;
	return 0;
	}

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

Next episode

Happy Coding