At Coder Educational DP-H | DP Series(Episode-10)

 Problem Description here

Problem: এই প্রব্লেমে আমাদেরকে n * m সাইজের একটি 2D গ্রীড দেয়া থাকবে যার কিছু সেল ফাঁকা এবং কিছু সেল ব্লকড। ফাঁকা সেলগুলো দিয়েই শুধু হাঁটা সম্ভব।

তোমাকে বের করতে হবে (1,1) সেল থেকে (n,m) সেলে যাওয়ার মোট কয়টি পাথ আছে যদি তুমি শুধুমাত্র নিচের এবং ডানের সেলে মুভ করতে পারো। 

Recursive Solution:

১) এই প্রব্লেমে স্টেট হবে দুটি। একটি আমি বর্তমানে গ্রীডের কত নং সারিতে আছি এবং অন্যটি কত নং কলামে আছি।

২) এরপর আমি বর্তমান সেল থেকে নিচের সেলে মুভ দিবো যদি সেটি ফাঁকা এবং গ্রীডের ভিতরে অবস্থিত হয় এবং বর্তমান সেল এর ডানের সেলে মুভ দিবো যদি সেটি ফাঁকা এবং গ্রীডের ভিতরে অবস্থিত হয়।

৩) যখন আমরা (n,m) সেলে পৌছাবো সেটি হবে বেস কেস। এবং বেস কেসে ১ রিটার্ন করবো। 

	#include<bits/stdc++.h>
	using namespace std;
	const int MOD = 1e9+7;
	long long h,w,dp[1005][1005]; /** State-1:row ; State-2:column **/
	char s[1005][1005];
	long long FuN(int pos1,int pos2)
	{
	if(pos1 == h-1 && pos2 == w-1)
	return 1LL;
	if(dp[pos1][pos2] != -1)
	return dp[pos1][pos2];
	long long ret1=0,ret2=0;
	if(pos1+1 < h && s[pos1+1][pos2] == '.')
	ret1 = FuN(pos1+1 , pos2) % MOD;
	if(pos2+1 < w && s[pos1][pos2+1] == '.')
	ret2 = FuN(pos1 , pos2+1) % MOD;
	return dp[pos1][pos2]=(ret1+ret2)%MOD;
	}
	int main()
	{
	memset(dp , -1 , sizeof(dp));
	long long i,j,ans;
	cin>>h>>w;
	for(i=0 ; i<h ; i++)
	scanf("%s",s[i]);
	ans=FuN(0,0);
	cout<<ans<<endl;
	return 0;
	}

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

Iterative Solution:

গত পর্বগুলো সব পড়ে আসলে এতোক্ষণে তুমি নিশ্চয়ই ইটারেটিভ ডিপি ভালোই বুঝো। যেকারণে বিস্তারিত ব্যাখ্যায় গেলাম না 😛

	#include<bits/stdc++.h>
	using namespace std;
	const int mod = 1e9+7;
	char grid[1005][1005];
	int dp[1005][1005];
	/** Here,dp[i][j] means number of path from (1,1) to (i,j) cell **/
	void addSelf(int &x,int y)
	{
	x += y;
	if(x >= mod)
	x -= mod;
	}
	int main()
	{
	int i,j,row,col,ans;
	cin>>row>>col;
	for(i=1 ; i<=row ; i++){
	for(j=1 ; j<=col ; j++)
	cin>>grid[i][j];
	}
	dp[1][1] = 1; ///Base case
	for(i=1 ; i<=row ; i++){
	for(j=1 ; j<=col ; j++){
	if(grid[i][j] == '#')
	continue;
	addSelf(dp[i][j] , dp[i-1][j]);
	addSelf(dp[i][j] , dp[i][j-1]);
	}
	}
	ans = dp[row][col];
	cout<<ans<<endl;
	return 0;
	}

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

Next Episode

Happy Coding