Introduction to expected value
এই পর্বে আমি কোডশেফ এর এক্সপেক্টেড ভ্যালুর টিউটোরিয়াল টির কিছু প্রব্লেম নিজের মতো করে সমাধান করার চেষ্টা করেছি।
হ্যাপি কোডিং 😊
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 সংখ্যক হেড পেলে টেল অপেক্ষা ...
Comments
Post a Comment