At Coder Educational DP-I | DP Series(Episode-11)

 Problem Description here

Problem: n সংখ্যক কয়েন দেয়া আছে। যেখানে ith কয়েন টস করলে হেড উঠার সম্ভাব্যতা P[i] এবং টেল উঠার সম্ভাব্যতা 1 - P[i]

সবগুলো কয়েন টস করলে টেল এর থেকে হেড বেশি পাওয়ার সম্ভাব্যতা কত সেটি বের করতে হবে। 

Recursive Solution:

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

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

৩) প্রতিটি সাব-প্রব্লেম এ হেড উঠলে টেল অপেক্ষা বেশি হেড পাওয়ার সম্ভাব্যতা কত বের করবো এবং টেল উঠলে টেল অপেক্ষা হেড বেশি পাওয়ার সম্ভাব্যতা কত বের করবো। এবং দুটি ফলাফল যোগ করবো। 

ভালোভাবে লক্ষ্য করলে বুঝবে যে এখানে আমরা টেল অপেক্ষা হেড বেশি পাওয়ার যে সম্ভাব্যতা সেটি রিটার্ন করছি সর্বদা।

dp[i][j] বলতে বোঝানো হচ্ছে 1st to ith পজিশন পর্যন্ত j সংখ্যক হেড পেলে টেল অপেক্ষা বেশি হেড পাওয়ার সম্ভাব্যতা কত।

	#include<bits/stdc++.h>
	using namespace std;
	int n;
	bool vis[3005][3005];
	double h_prob[3005],dp[3005][3005];
	///State-1: Position
	///State-2: Number of head till now
	double fun(int pos,int head)
	{
	if(pos > n){
	if(head > (n/2))
	return 1.0;
	else
	return 0.0;
	}
	if(vis[pos][head])
	return dp[pos][head];
	double ret1,ret2;
	ret1 = h_prob[pos] * fun(pos+1,head+1);
	ret2 = (1-h_prob[pos]) * fun(pos+1,head);
	return dp[pos][head]=ret1+ret2;
	}
	int main()
	{
	int i;
	double ans;
	memset(vis , 0 , sizeof(vis));
	cin>>n;
	for(i=1;i<=n;i++)
	cin>>h_prob[i];
	ans = fun(1,0);
	printf("%0.9f\n",ans);
	return 0;
	}

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

Iterative Solution:

১) ইটারেটিভ সল্যুশন এ i তম পজিশনে থাকা অবস্থায় dp[j] বলতে বোঝায় 1st to ith কয়েন পর্যন্ত  j সংখ্যক হেড পাওয়ার সম্ভাব্যতা। 

২) সবশেষে, nth পজিশনে (n+1)/2 থেকে শুরু করে n টা হেড পাওয়ার সম্ভাব্যতা যোগ করলেই আউটপুট পাওয়া যাবে।

	#include<bits/stdc++.h>
	using namespace std;
	double h_prob[3005],dp[3005];
	///dp[i] means probability of having i heads so far
	int main()
	{
	int i,j,k,n;
	double ans = 0.0;
	cin>>n;
	for(i=1 ; i<=n ; i++)
	cin>>h_prob[i];
	dp[0] = 1.0;
	for(int pos=1 ; pos<=n ; pos++){
	for(int head=pos ; head >= 0 ; head--)
	dp[head] = (dp[head-1] * h_prob[pos]) + (dp[head] * (1.0 - h_prob[pos]));
	}
	for(int head=(n+1)/2 ; head<=n ; head++)
	ans += dp[head];
	printf("%0.10f\n",ans);
	return 0;
	}

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

Next Episode

Happy Coding