मान लीजिए हमारे पास एक संख्या n है। तो मान लीजिए रसोई में n संतरे हैं और हम इन नियमों को बनाए रखते हुए हर दिन कुछ संतरे खाते हैं: 1. एक संतरा खाएं। 2. यदि n सम है, तो n/2 संतरे खाएं। 3. यदि n 3 से विभाज्य है तो 2*(n/3) संतरे खाएं। हम प्रत्येक दिन केवल एक विकल्प चुन सकते हैं। हमें n संतरे खाने के लिए न्यूनतम दिनों की संख्या ज्ञात करनी है।
इसलिए, यदि इनपुट है n = 10, तो आउटपुट 4 होगा क्योंकि
दिन 1 पर 1 संतरा खाएं, 10 - 1 = 9।
दिन 2 पर 6 संतरे खाएं, 9 - 2*(9/3) = 9 - 6 = 3।
दिन 3 पर 2 संतरे खाएं, 3 - 2*(3/3) = 3 - 2 = 1।
दिन 4 पर अंतिम संतरा खाएं 1 - 1 = 0।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक फ़ंक्शन fun() परिभाषित करें। यह n लेगा
यदि n memo में है, तो
memo[n] वापस करें
यदि n <= 2, तो
n वापस करें
memo[n] := 1 + (n mod 2 + fun(n//2)) और (n mod 3 + fun(n//3)) का न्यूनतम
memo[n] वापस करें
मुख्य विधि से, निम्न करें
memo := एक नया मैप
fun(n) वापस करें
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
def solve(n):
def fun(n):
if n in memo:
return memo[n]
if n <= 2:
return n
memo[n] = 1 + min(n % 2 + fun(n // 2), n % 3 + fun(n // 3))
return memo[n]
memo = {}
return fun(n)
n = 12
print(solve(n))
इनपुट
7, [5,1,4,3]
आउटपुट
4
