At Coder Educational DP-N | DP Series(Episode-22)

 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[lft...rgt] Slime টি কে দুইভাগে ভাগ করার কস্ট হবে csum[rgt] - csum[lft-1]

এবং ara[lft...rgt] Slime টি কে আমরা lft পজিশন থেকে rgt পজিশনের আগ পর্যন্ত যেকোন জায়গায় কেটে দুইভাগ করতে পারি। এবং সম্ভাব্য সকল পজিশনের জন্য ট্রাই করে কস্ট মিনিমাইজ করবো। 

	#include<bits/stdc++.h>
	using namespace std;
	long long n,ara[405],csum[405],dp[405][405];
	long long FuN(int lft,int rgt)
	{
	if(lft >= rgt)
	return 0LL;
	if(dp[lft][rgt] != -1)
	return dp[lft][rgt];
	long long ret = 1e18 , cuttingcost = csum[rgt] - csum[lft-1];
	for(int mid=lft ; mid < rgt ; mid++)
	ret = min(ret , cuttingcost + FuN(lft , mid) + FuN(mid+1 , rgt));
	return dp[lft][rgt] = ret;
	}
	int main()
	{
	cin>>n;
	for(int i=1 ; i<=n ; i++){
	cin>>ara[i];
	csum[i] = csum[i-1] + ara[i];
	}
	memset(dp , -1 , sizeof(dp));
	cout<<FuN(1 , n)<<endl;
	return 0;
	}

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

Iterative Solution:

ইতোপূর্বে আমরা ইন্টারভাল ডিপির একটি প্রব্লেম দেখেছি। এবং আমরা জানি, ইন্টারভাল ডিপির প্রব্লেমগুলো ছোট ছোট সাব-অ্যারের জন্য সলভ করে সেগুলো কম্বাইন করে বড় সাব-অ্যারের জন্য রেজাল্ট বের করি। 

এবং এই প্রব্লেম সলভ করার লজিক অলরেডি উপরে আলোচনা করে এসেছি। এবার কোড দেখা যাকঃ

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	ll ara[405],prefsum[405],dp[405][405];
	int main()
	{
	ll i,j,k,n,ans;
	cin>>n;
	for(i=1 ; i<=n ; i++){
	cin>>ara[i];
	prefsum[i] = prefsum[i-1] + ara[i];
	}
	for(ll sz=2 ; sz<=n ; sz++){
	for(i=1 ; i<=n-sz+1 ; i++){
	j = i+sz-1;
	dp[i][j] = 1e18;
	ll cuttingcost = prefsum[j] - prefsum[i-1];
	for(k=i ; k<j ; k++)
	dp[i][j] = min(dp[i][j] , cuttingcost + dp[i][k] + dp[k+1][j]);
	}
	}
	cout<<dp[1][n]<<endl;
	return 0;
	}

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

Click here to read next episode

Happy Coding