सिँढी चढ्ने: सम्झ, नदोहोर्याऊ
तपाईं सिँढी एक वा दुई खुड्किला गरी चढ्नुहुन्छ। माथिसम्म कति फरक तरिकाले पुग्न सकिन्छ? अघिल्ला उत्तरबाट एक-एक खुड्किला गरी उत्तर बनाउनुहोस्, र उत्तर बारम्बार निकाल्नुभन्दा सम्झेर राख्नु किन राम्रो हो, हेर्नुहोस्।
मूल अवधारणा
Dynamic programming ले ठूलो समस्या साना समस्याका उत्तरबाट हल गर्छ र ती उत्तर सम्झेर राख्छ: n खुड्किला चढ्ने तरिका, n − 1 का तरिका र n − 2 का तरिकाको योग हो
पाठ: Algorithm को दक्षता
मानौँ तपाईं सिँढी एक खुड्किला वा दुई खुड्किला गरी चढ्न सक्नुहुन्छ। एउटा खुड्किला 1 तरिकाले चढिन्छ, दुई खुड्किला 2 तरिकाले (1 + 1, वा 2)। अझ ठूलो सिँढीमा तपाईंको अन्तिम चाल या त n − 1 बाट एक खुड्किलाको, या n − 2 बाट दुई खुड्किलाको हुन्छ। त्यसैले n खुड्किलाका तरिका, n − 1 का तरिका र n − 2 का तरिकाको योग हो। सामान्य recursive प्रोग्रामले साना उत्तर बारम्बार निकाल्छ, अग्लो सिँढीका लागि करोडौँ पटक। Dynamic programming यसभन्दा चलाख छ: यसले तलबाट सुरु गर्छ, हरेक उत्तर एक पटक मात्र निकाल्छ, र सम्झेर राख्छ। यो प्रोग्रामले अन्तिम दुई उत्तर, prev र ways, मात्र सम्झन्छ र एक-एक खुड्किला माथि बढ्छ।
के सिक्नुहुनेछ
- ways(n) = ways(n − 1) + ways(n − 2) किन हुन्छ, व्याख्या गर्नुहोस्।
- prev, ways र next सहितको तलबाट माथिको loop trace गर्नुहोस्।
- उत्तर सम्झेर राख्दा किन काम बच्छ, व्याख्या गर्नुहोस्।
- सम्झेका दुई उत्तर अद्यावधिक गर्ने लाइनहरू क्रममा राख्नुहोस्।
सुरु गर्नुअघि
- For loop र variable कसरी काम गर्छन्, थाहा हुनुपर्छ।
सामग्री
- 1, 2, 3 र 4 खुड्किलाका तरिका हातले लेख्न कापी
उपकरण
- केही पनि चाहिँदैन
विधि
- 5 खुड्किलाका लागि प्रोग्राम चलाएर हरेक खुड्किलाका तरिका पढ्नुहोस्।
- एक-एक चरण चलाएर prev र ways माथि सरेको हेर्नुहोस्।
- 10 खुड्किला चलाएर हेर्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।