DP Optimization(Part-3) | DP Series(Episode-17)

 এই পর্বে আমরা মূলত প্রিফিক্স সাম এর মাধ্যমে ডিপির টাইম কমপ্লেক্সিটি অপটিমাইজেশন দেখবো। যা অনেক ডিপি প্রব্লেমেই কাজে লাগতে পারে। 

প্রব্লেমঃ

একটি 1*n আকারের গ্রীডের প্রতি সেলে কিছু ভ্যালু a[i] আছে। একটি সেল i থেকে a[i] দূরত্বের মধ্যে সামনে অথবা পিছনের কোন সেলে জাম্প দেয়া যায়। বলতে হবে সেল 1 থেকে সেল n এ এক্সেক্টলি k সংখ্যক জাম্প দিয়ে কতভাবে যাওয়া যায়?

প্রথমেই এই প্রব্লেমের যে সল্যুশন আমাদের মাথায় আসে তা অনেকটা এরকমঃ 

	#include<bits/stdc++.h>
	using namespace std;
	int n,k,a[105],dp[105][105];
	/** Here, dp[i][j] means number of ways to go from ith to nth cell using exactly j steps **/
	void FuN()
	{
	dp[n][0] = 1;
	for(int step=1 ; step<=k ; step++){
	for(int i=1 ; i<=n ; i++){
	for(int x=i+1 ; x <= min(i+a[i] , n) ; x++)
	dp[i][step] += dp[x][step-1];
	for(int x=i-1 ; x >= max(1 , i-a[i]) ; x--)
	dp[i][step] += dp[x][step-1];
	}
	}
	cout<<dp[1][k]<<endl;
	}
	int main()
	{
	cin>>n>>k;
	for(int i=1 ; i<=n ; i++)
	cin>>a[i];
	FuN();
	return 0;
	}

view raw Optimized DP-3.1.cpp hosted with ❤ by GitHub

এখন, n<=10^4, k<=10^4 হলে উপরোক্ত সল্যুশন আর কাজ করবে না! এখন, ১২ এবং ১৫ নম্বর লাইনের ফর লুপ এর দিকে ভালো করে লক্ষ্য কর। 

লক্ষ্য করলে বুঝবে যে এই লুপ দুইটির কাজ আমরা প্রিফিক্স সাম ক্যালকুলেট করে O(1)  কমপ্লেক্সিটি তে করতে পারি। তখন কোডটি দেখতে এরকম হবেঃ 

	#include<bits/stdc++.h>
	using namespace std;
	int n,k,a[10005],dp[10005][10005];
	/** Here, dp[i][j] means number of ways to go from ith to nth cell using exactly j steps **/
	void FuN()
	{
	dp[n][0] = 1;
	for(int step=1 ; step<=k ; step++){
	vector<int>prefix(n+1);
	for(int i=1 ; i<=n ; i++)
	prefix[i] = prefix[i-1] + dp[i][step-1];
	for(int i=1 ; i<=n ; i++){
	int r = min(i+a[i] , n);
	int l = max(1 , i-a[i]);
	dp[i][step] += ((prefix[r] - prefix[l-1]) - dp[i][step-1]);
	}
	}
	cout<<dp[1][k]<<endl;
	}
	int main()
	{
	cin>>n>>k;
	for(int i=1 ; i<=n ; i++)
	cin>>a[i];
	FuN();
	return 0;
	}

view raw Optimized DP-3.2.cpp hosted with ❤ by GitHub

এখন, উপরের সল্যুশন এ আমাদের মেমোরি লাগে প্রায় ৩৮১ মেগাবাইট। অর্থাৎ, MLE খাওয়ার সম্ভাবনা খুবই বেশি। 

আগের দুইটি পর্ব পড়ে থাকলে নিজে নিজে এই সল্যুশনটিকে মেমোরি অপ্টিমাইজ করার চেষ্টা কর। 

মেমোরি অপ্টিমাইজ করার পর সল্যুশনটা দেখতে এরকম হবেঃ 

	#include<bits/stdc++.h>
	using namespace std;
	int n,k,a[10005],dp[10005][2];
	void FuN()
	{
	dp[n][0] = 1;
	for(int step=1 ; step<=k ; step++){
	vector<int>prefix(n+1);
	for(int i=1 ; i<=n ; i++) dp[i][step & 1] = 0;
	for(int i=1 ; i<=n ; i++)
	prefix[i] = prefix[i-1] + dp[i][(step-1) & 1];
	for(int i=1 ; i<=n ; i++){
	int r = min(i+a[i] , n);
	int l = max(1 , i-a[i]);
	dp[i][step & 1] += ((prefix[r] - prefix[l-1]) - dp[i][(step-1) & 1]);
	}
	}
	cout<<dp[1][k & 1]<<endl;
	}
	int main()
	{
	cin>>n>>k;
	for(int i=1 ; i<=n ; i++)
	cin>>a[i];
	FuN();
	return 0;
	}

view raw Optimized DP-3.3.cpp hosted with ❤ by GitHub

Next Episode

Happy Coding😀