DP Optimization(Part-2) | DP Series(Episode-16)

গত পর্বের মতো এই পর্বেও আমরা মেমোরি অপ্টিমাইজেশন দেখবো। 

প্রব্লেমঃ মনে করি, আমাকে একটি n * m গ্রীড দেয়া আছে যেখানে n<=10^4 এবং m<=10^4। গ্রীডের প্রতিটি সেলে দুই ধরণের ক্যারেক্টার থাকতে পারে। '.' মানে ফাঁকা সেল এবং '#' মানে দেয়াল। গ্রীডের (1,1) সেল থেকে গ্রীডের (n,m) সেলে যাওয়ার মোট কয়টি পাথ আছে তা বের করতে হবে। প্রতিটি সেল থেকে আমি নিচে অথবা ডানে মুভ দিতে পারবো। 

এন্সার খুব বড় হতে পারে তাই এন্সার কে 10^9 + 7 দ্বারা মড করতে হবে। 

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

	#include<bits/stdc++.h>
	using namespace std;
	const int mod = 1e9+7;
	int row,col,dp[10005][10005];
	char grid[10005][10005];
	void addSelf(int &x,int y)
	{
	x += y;
	if(x >= mod)
	x -= mod;
	}
	void FuN()
	{
	for(int i=1 ; i<=row ; i++){
	for(int j=1 ; j<=col ; j++){
	if(grid[i][j] == '#')
	continue;
	if(i == 1 && j == 1)
	dp[i][j] = 1;
	else{
	addSelf(dp[i][j] , dp[i-1][j]);
	addSelf(dp[i][j] , dp[i][j-1]);
	}
	}
	}
	cout<<dp[row][col]<<endl;
	}
	int main()
	{
	cin>>row>>col;
	for(int i=1 ; i<=row ; i++){
	for(int j=1 ; j<=col ; j++)
	cin>>grid[i][j];
	}
	FuN();
	return 0;
	}

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

একটু হিসেব করলেই দেখতে পাবা এই কোডে আমার মেমোরি লাগে প্রায় ৫৭২ মেগাবাইট!!!

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

এখন, কোডের ২৪ এবং ২৫ নম্বর লাইন যদি দেখো তাহলে দেখবে আমাকে বর্তমান সারির ডিপি ভ্যালু নির্ণয়ের জন্য আগের সারির ডিপি ভ্যালু জানতে হবে। অর্থাৎ, ith সারির জন্য শুধু (i-1)th সারির ভ্যালু জানাই যথেষ্ট। (i-2)th, (i-3)th,....এসব সারি আমার আর কোন কাজে লাগবে না। 

এখন, আগের পর্বটি পড়ে থাকলে নিশ্চয়ই এতোক্ষণে বুঝে গেছো কিভাবে dp[10005][10005] এর পরিবর্তে dp[2][10005] দিয়েই আমাদের প্রব্লেমটা সলভ করা যায়।

এতে, আমাদের মেমোরি লাগবে প্রায় ১৯১ মেগাবাইট!!! হিউজ মেমোরি অপ্টিমাইজড সল্যুশন!!!

এখনো না বুঝলে কোড দেখতে পারোঃ

	#include<bits/stdc++.h>
	using namespace std;
	const int mod = 1e9+7;
	int row,col,dp[2][10005];
	char grid[10005][10005];
	void addSelf(int &x,int y)
	{
	x += y;
	if(x >= mod)
	x -= mod;
	}
	void FuN()
	{
	for(int i=1 ; i<=row ; i++){
	for(int j=1 ; j<=col ; j++)
	dp[i & 1][j] = 0;
	for(int j=1 ; j<=col ; j++){
	if(grid[i][j] == '#'){
	dp[i & 1][j] = 0;
	continue;
	}
	if(i == 1 && j == 1)
	dp[i & 1][j] = 1;
	else{
	addSelf(dp[i & 1][j] , dp[(i-1) & 1][j]);
	addSelf(dp[i & 1][j] , dp[i & 1][j-1]);
	}
	}
	}
	cout<<dp[row & 1][col]<<endl;
	}
	int main()
	{
	cin>>row>>col;
	for(int i=1 ; i<=row ; i++){
	for(int j=1 ; j<=col ; j++)
	cin>>grid[i][j];
	}
	FuN();
	return 0;
	}

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

Suggested Problem: Click here

Next Episode

Happy Coding😃