आइए एक खेल पर विचार करें, जिसमें एक खिलाड़ी प्रत्येक चाल में 3, 5 या 10 से कुछ स्कोर प्राप्त कर सकता है। एक लक्ष्य स्कोर भी दिया गया है। हमारा कार्य उन तीन अंकों के साथ उस लक्ष्य स्कोर तक पहुंचने के संभावित तरीकों की संख्या ढूंढना है।
डायनामिक प्रोग्रामिंग दृष्टिकोण द्वारा, हम 0 से n तक के सभी स्कोर की एक सूची बनाएंगे, और 3, 5, 10 के प्रत्येक मान के लिए, हम बस तालिका को अपडेट करते हैं।
इनपुट और आउटपुट
इनपुट: 3, 5 और 10 का उपयोग करके पहुंचने के लिए अधिकतम स्कोर। मान लें इनपुट 50 है। आउटपुट: (3, 5, 10) का उपयोग करके पहुंचने के तरीकों की संख्या 50: 14
एल्गोरिदम
countWays(n)
केवल 3 संभावित स्कोर हैं, वे 3, 5 और 10 हैं
इनपुट: n वह अधिकतम स्कोर है जिसे पहुंचना है।
आउटपुट: स्कोर n तक पहुंचने के संभावित तरीकों की संख्या।
शुरू आकार n+1 की तालिका बनाएं सभी तालिका प्रविष्टियों को 0 पर सेट करें table[0] := 1 i := 3 से n तक, करें table[i] := table[i] + table[i-3] किया i := 5 से n तक, करें table[i] := table[i] + table[i-5] किया i := 10 से n तक, करें table[i] := table[i] + table[i-10] किया table[n] वापस करें अंत
उदाहरण
#include <iostream> using namespace std; // स्कोर n तक पहुंचने के तरीकों की संख्या लौटाता है int countWay(int n) { int table[n+1], i; //प्रत्येक i के मान के लिए गिनती संग्रहीत करने के लिए तालिका for(int i = 0; i<=n; i++) { table[i] = 0; //सभी तालिका मानों को 0 से आरंभ करें } table[0] = 1; //इनपुट 0 के लिए 1 सेट करें for (i=3; i<=n; i++) //3 का उपयोग करके हल करने का प्रयास करें table[i] += table[i-3]; for (i=5; i<=n; i++) //5 का उपयोग करके हल करने का प्रयास करें table[i] += table[i-5]; for (i=10; i<=n; i++) //10 का उपयोग करके हल करने का प्रयास करें table[i] += table[i-10]; return table[n]; } int main() { int n; cout << "Enter max score: "; cin >> n; cout << "Number of ways to reach using (3, 5, 10)" << n <<": " << countWay(n); }
आउटपुट
Enter max score: 50 Number of ways to reach using (3, 5, 10)50: 14
