dynamic-programming ट्यूटोरियल
गतिशील-प्रोग्रामिंग के साथ शुरुआत करना

टिप्पणियों

परिचय गतिशील प्रोग्रामिंग के लिए

डायनेमिक प्रोग्रामिंग सबप्रॉब्लम्स के समाधानों को जोड़कर समस्याओं को हल करता है। यह विभाजित करने और जीतने की विधि के अनुरूप हो सकता है, जहां समस्या को असम्पीडित उपप्रकारों में विभाजित किया जाता है, उपप्रवर्तियों को पुन: हल किया जाता है और फिर मूल समस्या का समाधान खोजने के लिए संयुक्त किया जाता है। इसके विपरीत, डायनेमिक प्रोग्रामिंग तब लागू होती है जब सबप्रॉम्बल्म ओवरलैप करते हैं - यानी, जब सबप्रॉबल्म सबबप्रॉफल्म्स साझा करते हैं। इस संदर्भ में, एक डिवाइड-एंड-कॉनकॉर एल्गोरिथ्म आवश्यक से अधिक काम करता है, बार-बार सामान्य उप-प्रजाति को हल करना। डायनेमिक-प्रोग्रामिंग एल्गोरिथ्म प्रत्येक उप-प्रजाति को एक बार में हल करता है और फिर एक तालिका में इसके उत्तर को बचाता है, जिससे प्रत्येक उप-उपप्रकारों को हल करने पर हर बार उत्तर को पुन: प्रकाशित करने के कार्य से बचा जाता है।

आइए एक उदाहरण देखें। इतालवी गणितज्ञ लियोनार्डो पिसानो बिगोलो , जिन्हें हम आमतौर पर फाइबोनैचि के नाम से जानते हैं, ने खरगोशों की आबादी के आदर्श विकास पर विचार करके एक संख्या श्रृंखला की खोज की। श्रृंखला है:

1, 1, 2, 3, 5, 8, 13, 21, ......

हम देख सकते हैं कि पहले दो के बाद की प्रत्येक संख्या दो पूर्ववर्ती संख्याओं का योग है। अब, एक फंक्शन बनाते हैं F (n) जो हमें nth फाइबोनैचि संख्या लौटाएगा, अर्थात

F(n) = nth Fibonacci Number

अब तक, हम जानते हैं कि,

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

हम इसे सामान्यीकृत कर सकते हैं:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

अब अगर हम इसे एक पुनरावर्ती कार्य के रूप में लिखना चाहते हैं, तो हमारे पास आधार आधार के रूप में F(1) और F(2) । तो हमारा फिबोनाची समारोह होगा:

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

अब अगर हम F(6) , तो यह F(5) और F(4) , जो कुछ और कॉल करेगा। आइए इसका चित्रण करें:

तस्वीर से, हम देख सकते हैं कि F(6) F(5) और F(4) को कॉल करेगा। अब F(5) को F(4) और F(3) कहेंगे। F(5) गणना के बाद, हम निश्चित रूप से कह सकते हैं कि F(5) द्वारा बुलाए गए सभी कार्यों की गणना पहले ही की जा चुकी है। इसका मतलब है, हम पहले ही F(4) गणना कर चुके हैं। लेकिन हम फिर से F(4) गणना कर रहे हैं क्योंकि F(6) का सही बच्चा इंगित करता है। क्या हमें वास्तव में पुनर्गणना करने की आवश्यकता है? हम क्या कर सकते हैं, एक बार जब हमने F(4) के मूल्य की गणना की है, तो हम इसे डीपी नामक एक सरणी में संग्रहीत करेंगे, और जब आवश्यकता होगी, तब इसका पुन: उपयोग करेंगे। हम -1 (या हमारी गणना में नहीं आने वाले किसी भी मूल्य) के साथ हमारे dp सरणी को आरंभीकृत करेंगे। तब हम F (6) को कॉल करेंगे जहाँ हमारा संशोधित F (n) दिखेगा:

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

हमने पहले जैसा ही कार्य किया है, लेकिन एक साधारण अनुकूलन के साथ। यही है, हमने संस्मरण तकनीक का उपयोग किया है। सबसे पहले, dp सरणी के सभी मान -1 होंगे । जब F(4) कहा जाता है, तो हम जांचते हैं कि यह खाली है या नहीं। अगर यह -1 स्टोर करता है, तो हम इसके मूल्य की गणना करेंगे और इसे dp [4] में स्टोर करेंगे। अगर यह कुछ भी स्टोर करता है लेकिन -1 , इसका मतलब है कि हम पहले ही इसकी कीमत की गणना कर चुके हैं। तो हम केवल मान वापस करेंगे।

संस्मरण का उपयोग करते हुए इस सरल अनुकूलन को डायनामिक प्रोग्रामिंग कहा जाता है।

डायनेमिक प्रोग्रामिंग का उपयोग करके एक समस्या को हल किया जा सकता है यदि इसमें कुछ विशेषताएं हैं। य़े हैं:

• subproblems:
  एक डीपी समस्या को एक या एक से अधिक उपप्रकारों में विभाजित किया जा सकता है। उदाहरण के लिए: F(4) को छोटे सबप्रोब्लेम्स F(3) और F(2) में विभाजित किया जा सकता है। जैसा कि उपप्रोफ़ेल्स हमारी मुख्य समस्या के समान हैं, इन्हें एक ही तकनीक का उपयोग करके हल किया जा सकता है।
• ओवरलैपिंग उपप्रोग्राम:
  एक डीपी समस्या में अतिव्यापी उपप्रकार होना चाहिए। इसका मतलब है कि कुछ सामान्य हिस्सा होना चाहिए जिसके लिए एक ही फ़ंक्शन को एक से अधिक बार कहा जाता है। उदाहरण के लिए: F(5) और F(6) में F(3) और F(4) आम है। यही कारण है कि हमने अपने सरणी में मान संग्रहीत किए हैं।

• इष्टतम निर्माण:
  मान लीजिए कि आपको फ़ंक्शन g(x) को छोटा करने के लिए कहा गया है। आप जानते हैं कि g(x) का मान g(y) और g(z) पर निर्भर करता है। अब अगर हम g(y) और g(z) दोनों को कम करके g(x) को कम कर सकते हैं, तभी हम कह सकते हैं कि समस्या का इष्टतम उपप्रकार है। यदि g(x) केवल कम करके कम से कम है g(y) और यदि कम से कम या अधिकतम g(z) पर कोई असर नहीं होता है g(x) है, तो इस समस्या को इष्टतम उपसंरचना जरूरत नहीं है। सरल शब्दों में, यदि किसी समस्या का इष्टतम समाधान उसके उपप्रक्रम के इष्टतम समाधान से पाया जा सकता है, तो हम कह सकते हैं कि समस्या में इष्टतम उप-गुण संपत्ति है।

डायनामिक प्रोग्रामिंग में राज्य को समझना

एक उदाहरण के साथ चर्चा करते हैं। N आइटम से, कितने तरीकों से आप r आइटम चुन सकते हैं? तुम्हें पता है कि यह द्वारा चिह्नित है । अब एक आइटम के बारे में सोचो।

• यदि आप आइटम का चयन नहीं करते हैं, तो उसके बाद आपको शेष n-1 आइटम से r आइटम लेना होगा, जो इसके द्वारा दिया गया है ।
• यदि आप आइटम का चयन करते हैं, तो उसके बाद आपको शेष n-1 आइटम से r-1 आइटम लेना होगा, जो इसके द्वारा दिया गया है ।

इन दोनों का योग हमें कुल तरीकों की संख्या देता है। अर्थात्:

अगर हम nCr(n,r) को एक फ़ंक्शन के रूप में सोचते हैं जो n और r को पैरामीटर और निर्धारित के रूप में लेता है , हम उपर्युक्त संबंध लिख सकते हैं:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

यह एक पुनरावर्ती संबंध है। इसे समाप्त करने के लिए, हमें बेस केस (एस) निर्धारित करने की आवश्यकता है। हम जानते हैं कि, तथा । इन दोनों को आधार मामलों के रूप में उपयोग करना, हमारे एल्गोरिदम को निर्धारित करना है होगा:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

यदि हम प्रक्रिया को रेखांकन के आधार पर देखते हैं, तो हम देख सकते हैं कि कुछ पुनरावर्ती को एक से अधिक बार कहा जाता है। उदाहरण के लिए: यदि हम n = 8 और r = 5 लेते हैं, तो हम प्राप्त करते हैं:

हम एक सरणी, dp का उपयोग करके इस दोहराया कॉल से बच सकते हैं। चूंकि 2 पैरामीटर हैं, हमें 2 डी सरणी की आवश्यकता होगी। हम -1 के साथ dp सरणी को इनिशियलाइज़ करेंगे, जहाँ -1 का अर्थ है कि अभी तक गणना नहीं की गई है। हमारी प्रक्रिया होगी:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

संकल्प करना , हम दो मापदंडों n और r की जरूरत है । इन मापदंडों को राज्य कहा जाता है । हम केवल यह कह सकते हैं कि राज्यों की संख्या dp सरणी के आयाम की संख्या निर्धारित करती है। सरणी का आकार हमारी आवश्यकता के अनुसार बदल जाएगा। हमारे गतिशील प्रोग्रामिंग एल्गोरिदम निम्नलिखित सामान्य पैटर्न बनाए रखेंगे:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

राज्य का निर्धारण गतिशील प्रोग्रामिंग का सबसे महत्वपूर्ण हिस्सा है। इसमें कई पैरामीटर शामिल हैं जो हमारी समस्या को परिभाषित करते हैं और उनकी गणना को अनुकूलित करते हुए, हम पूरी समस्या का अनुकूलन कर सकते हैं।

एक डीपी समाधान का निर्माण

डायनेमिक प्रोग्रामिंग (DP) का उपयोग करके आप चाहे कितनी भी समस्याएं हल कर लें, लेकिन यह आपको आश्चर्यचकित कर सकता है। लेकिन जीवन में सब कुछ के रूप में, अभ्यास आपको बेहतर बनाता है। इन्हें ध्यान में रखते हुए, हम DP समस्याओं के समाधान के निर्माण की प्रक्रिया देखेंगे। इस विषय पर अन्य उदाहरण आपको यह समझने में मदद करेंगे कि डीपी क्या है और यह कैसे काम करता है। इस उदाहरण में, हम यह समझने की कोशिश करेंगे कि खरोंच से डीपी समाधान के साथ कैसे आना है।

पुनरावर्ती बनाम पुनरावर्ती:
डीपी समाधान के निर्माण की दो तकनीकें हैं। वो हैं:

• Iterative (चक्र के लिए उपयोग)
• पुनरावर्ती (पुनरावर्तन का उपयोग करके)

उदाहरण के लिए, दो तार s1 और s2 के सबसे लंबे समय तक सामान्य उप- लंबाई की गणना के लिए एल्गोरिथ्म इस तरह दिखेगा:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

यह एक पुनरावृत्त समाधान है। इस तरह से कोडित किए जाने के कुछ कारण हैं:

• पुनरावृत्ति की तुलना में Iteration तेज है।
• समय और स्थान की जटिलता का निर्धारण आसान है।
• सोर्स कोड छोटा और साफ है

स्रोत कोड को देखकर, आप आसानी से समझ सकते हैं कि यह कैसे और क्यों काम करता है, लेकिन यह समझना मुश्किल है कि इस समाधान के साथ कैसे आना है। हालांकि ऊपर वर्णित दो दृष्टिकोण दो अलग-अलग छद्म कोड में तब्दील हो जाते हैं। एक पुनरावृत्ति (नीचे-ऊपर) का उपयोग करता है और दूसरा पुनरावृत्ति (टॉप-डाउन) दृष्टिकोण का उपयोग करता है। बाद वाले को ज्ञापन तकनीक के रूप में भी जाना जाता है। हालांकि, दो समाधान कम या ज्यादा समतुल्य हैं और एक को आसानी से दूसरे में बदला जा सकता है। इस उदाहरण के लिए, हम बताएंगे कि किसी समस्या के पुनरावर्ती समाधान के साथ कैसे आना चाहिए।

उदाहरण समस्या:
मान लीजिए, आपके पास N ( 1, 2, 3, ...., N ) वाइन है जो एक शेल्फ पर एक दूसरे के बगल में रखी गई है। I th वाइन की कीमत p [i] है । मदिरा की कीमत हर साल बढ़ती है। मान लीजिए कि यह वर्ष 1 है , वर्ष y पर I वें वाइन की कीमत होगी: वर्ष * वाइन की कीमत = y * p [I] । आप अपने पास मौजूद वाइन को बेचना चाहते हैं, लेकिन आपको इस साल से शुरू करके प्रति वर्ष बिल्कुल एक वाइन बेचना होगा। फिर से, प्रत्येक वर्ष, आपको केवल सबसे बाईं या दाईं शराब बेचने की अनुमति दी जाती है और आप वाइन को पुनर्व्यवस्थित नहीं कर सकते हैं, इसका मतलब है कि उन्हें उसी क्रम में रहना चाहिए जैसे वे शुरुआत में हैं।

उदाहरण के लिए: मान लें कि आपके पास शेल्फ में 4 वाइन हैं, और उनकी कीमतें हैं (बाएं से दाएं):

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

इष्टतम समाधान 1 -> 4 -> 3 -> 2 क्रम में मदिरा बेचना होगा, जिससे हमें कुल लाभ होगा:

लालची दृष्टिकोण:
थोड़ी देर के लिए मंथन करने के बाद, आप संभव के रूप में देर से महंगी शराब बेचने के समाधान के साथ आ सकते हैं। तो आपकी लालची रणनीति यह होगी:

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

हालांकि रणनीति में यह उल्लेख नहीं है कि जब दोनों वाइन की कीमत एक ही हो, तो रणनीति थोड़े सही लगती है। लेकिन दुर्भाग्य से, यह नहीं है। यदि मदिरा की कीमतें हैं:

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

लालची रणनीति उन्हें 1 -> 2 -> 5 -> 4 -> 3 के कुल लाभ में बेच देगी:

लेकिन हम बेहतर कर सकते हैं यदि हम ऑर्डर के कुल लाभ के लिए 1 -> 5 -> 4 -> 2 -> 3 में वाइन बेचते हैं:

इस उदाहरण से आपको यह समझाना चाहिए कि समस्या इतनी आसान नहीं है क्योंकि यह पहली नजर में दिखती है। लेकिन इसे डायनेमिक प्रोग्रामिंग का उपयोग करके हल किया जा सकता है।

उलटे पांव लौटने से:
एक समस्या के लिए संस्मरण समाधान के साथ आने के लिए बैकट्रैक समाधान ढूंढना आसान है। Backtrack समाधान समस्या के लिए सभी मान्य उत्तरों का मूल्यांकन करता है और सबसे अच्छे को चुनता है। अधिकांश समस्याओं के लिए इस तरह के समाधान के साथ आना आसान है। बैकट्रैक सॉल्यूशन से संपर्क करने के लिए तीन रणनीतियां हो सकती हैं:

1. यह एक फ़ंक्शन होना चाहिए जो पुनरावृत्ति का उपयोग करके उत्तर की गणना करता है।
2. यह उत्तर विवरणी के साथ वापस करना चाहिए।
3. सभी गैर-स्थानीय चर को केवल-पढ़ने के लिए उपयोग किया जाना चाहिए, अर्थात फ़ंक्शन केवल स्थानीय चर और उसके तर्कों को संशोधित कर सकता है।

हमारी उदाहरण की समस्या के लिए, हम सबसे बाईं या दाईं शराब बेचने की कोशिश करेंगे और उत्तर की गणना करके बेहतर को वापस करेंगे। पीछे के समाधान की तरह दिखेगा:

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

यदि हम profitDetermination(1, 0, n-1) का उपयोग करके प्रक्रिया को कॉल करते हैं, जहां n वाइन की कुल संख्या है, तो यह जवाब वापस कर देगा।

यह समाधान वाइन बेचने के सभी संभव वैध संयोजनों का प्रयास करता है। यदि शुरुआत में एन वाइन हैं, तो यह जांच करेगा संभावनाओं। भले ही हमें अब सही उत्तर मिल जाए, लेकिन एल्गोरिथ्म की समय जटिलता तेजी से बढ़ती है।

सही ढंग से लिखा गया बैकट्रैक फ़ंक्शन हमेशा एक अच्छी तरह से वर्णित प्रश्न के उत्तर का प्रतिनिधित्व करना चाहिए। हमारे उदाहरण में, प्रक्रिया profitDetermination प्रश्न के उत्तर का प्रतिनिधित्व करता है: सरणी पी में संग्रहीत कीमतों के साथ वाइन को बेचने से हमें सबसे अच्छा लाभ क्या हो सकता है, जब वर्तमान वर्ष वर्ष है और बिना बिके वाइन के अंतराल के माध्यम से शुरू होता है। , अंत], समावेशी? आपको हमेशा अपने बैकट्रैक फ़ंक्शन के लिए इस तरह का प्रश्न बनाने की कोशिश करनी चाहिए कि क्या आपको यह सही लगा और समझ में आया कि यह क्या करता है।

निर्धारण राज्य:
राज्य डीपी समाधान में उपयोग किए जाने वाले मापदंडों की संख्या है। इस चरण में, हमें यह सोचने की आवश्यकता है कि आप फ़ंक्शन में कौन से तर्क पास करते हैं, निरर्थक हैं, अर्थात हम उन्हें अन्य तर्कों से बना सकते हैं या हमें उनकी बिल्कुल आवश्यकता नहीं है। यदि इस तरह के कोई तर्क हैं, तो हमें उन्हें फ़ंक्शन में पास करने की आवश्यकता नहीं है, हम उन्हें फ़ंक्शन के अंदर की गणना करेंगे।

उदाहरण फ़ंक्शन profitDetermination ऊपर दिखाया गया है, तर्क year निरर्थक है। यह उन वाइन की संख्या के बराबर है जिन्हें हम पहले ही बेच चुके हैं। यह शुरुआत की माइनस वाइन की कुल संख्या का उपयोग करके निर्धारित किया जा सकता है। यदि हम एक वैश्विक चर के रूप में वाइन एन की कुल संख्या को संग्रहीत करते हैं, तो हम निम्न कार्य को फिर से लिख सकते हैं:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

हमें एक वैध इनपुट से प्राप्त होने वाले मापदंडों के संभावित मूल्यों की सीमा के बारे में भी सोचना चाहिए। हमारे उदाहरण में, प्रत्येक पैरामीटर begin और end होता है जिसमें 0 से n-1 तक मान शामिल हो सकते हैं। एक वैध इनपुट में, हम भी begin <= end + 1 उम्मीद करेंगे begin <= end + 1 । हमारे फ़ंक्शन के साथ O(n²) विभिन्न तर्क हो सकते हैं।

Memoization:
हम अब लगभग हो चुके हैं। समय जटिलता के साथ पीछे के समाधान को बदलने के लिए समय जटिलता के साथ संस्मरण समाधान में , हम एक छोटी सी चाल का उपयोग करेंगे जिसके लिए बहुत प्रयास की आवश्यकता नहीं है।

जैसा कि ऊपर उल्लेख किया गया है, केवल हैं हमारे कार्य को विभिन्न मापदंडों के साथ बुलाया जा सकता है। दूसरे शब्दों में, केवल हैं विभिन्न चीजें जिन्हें हम वास्तव में गणना कर सकते हैं। तो कहाँ करता है समय जटिलता से आता है और यह क्या गणना करता है !!

इसका उत्तर है: घातीय समय जटिलता पुनरावृत्ति से आती है और उसी के कारण, यह बार-बार समान मूल्यों की गणना करता है। यदि आप n = 20 वाइन की एक मनमानी सरणी के लिए ऊपर उल्लिखित कोड चलाते हैं और गणना करते हैं कि तर्कों को शुरू होने के लिए कितनी बार फ़ंक्शन शुरू किया गया = 10 और अंत = 10 , तो आपको 92378 नंबर मिलेगा। यही कारण है कि कई बार एक ही जवाब की गणना करने के लिए समय की एक बड़ी बर्बादी है। हम इसे बेहतर बनाने के लिए क्या कर सकते हैं मानों को एक बार संग्रहीत करने के बाद हमने उन्हें गणना की है और हर बार फ़ंक्शन पहले से गणना की गई मूल्य के लिए पूछता है, हमें फिर से पूरी पुनरावर्तन चलाने की आवश्यकता नहीं है। हमारे पास एक सरणी dp [N] [N] होगा , इसे -1 से आरंभ करें (या कोई भी मान जो हमारी गणना में नहीं आएगा), जहां -1 का अर्थ है कि अभी तक गणना नहीं की गई है। सरणी के आकार शुरू और समाप्त कुछ शुरू करते हैं और हमारे सरणी में अंत मूल्यों के रूप में हम इसी मान संग्रहीत करता हूँ की अधिकतम संभव मूल्य से निर्धारित होता है। हमारी प्रक्रिया इस तरह दिखाई देगी:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

यह हमारा आवश्यक डीपी समाधान है। हमारी बहुत सरल चाल से, समाधान चलता है समय, क्योंकि वहाँ हैं हमारे फंक्शन को अलग-अलग मापदंडों से बुलाया जा सकता है और उनमें से प्रत्येक के लिए, फंक्शन केवल एक बार साथ चलता है जटिलता।

Summery:
यदि आप DP के उपयोग से हल की जा सकने वाली समस्या की पहचान कर सकते हैं, तो DP समाधान बनाने के लिए निम्नलिखित चरणों का उपयोग करें:

• सही उत्तर प्रदान करने के लिए एक बैकट्रैक फ़ंक्शन बनाएं।
• निरर्थक तर्कों को हटा दें।
• फ़ंक्शन मापदंडों के संभावित मूल्यों की अधिकतम सीमा का अनुमान लगाएं और कम से कम करें।
• एक फ़ंक्शन कॉल की समय जटिलता को अनुकूलित करने का प्रयास करें।
• मानों को संग्रहीत करें ताकि आपको इसकी दो बार गणना न करनी पड़े।

डीपी समाधान की जटिलता है: प्रत्येक कॉल के * समय जटिलता के साथ फ़ंक्शन को संभावित मानों की श्रेणी कहा जा सकता है ।