समस्या
मान लीजिए हमारे पास विभिन्न मूल्यवर्ग के सिक्के हैं और धन की कुल राशि amount है। हमें एक फ़ंक्शन परिभाषित करना है जो उस राशि को बनाने के लिए आवश्यक न्यूनतम सिक्कों की संख्या की गणना करता है। जब वह राशि सिक्कों के किसी भी संयोजन द्वारा नहीं बनाई जा सकती, तो -1 लौटाएं। उदाहरण के लिए, यदि इनपुट [1,2,5] है, और राशि 11 है, तो आउटपुट 3 होगा। यह 5 + 5 + 1 = 11 का उपयोग करके बनता है।
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- यदि amount = 0, तो 0 लौटाएं
- यदि सिक्कों की सरणी का न्यूनतम > amount, तो -1 लौटाएं
- dp नामक एक सरणी परिभाषित करें, आकार amount + 1, और इसे -1 से भरें
- सिक्कों की सरणी में i के लिए लूप
- यदि i > dp की लंबाई - 1, तो अगला भाग छोड़ें, अगले पुनरावृत्ति के लिए जाएं
- dp[i] := 1
- j को i + 1 से amount तक लूप में
- यदि dp[j - 1] = -1, तो अगला भाग छोड़ें, अगले पुनरावृत्ति के लिए जाएं
- अन्यथा यदि dp[j] = -1, तो dp[j] := dp[j - i] + 1
- अन्यथा dp[j] := dp[j] और dp[j - i] + 1 का न्यूनतम
- dp[amount] लौटाएं
उदाहरण (Python):
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
class Solution(object): def coinChange(self, coins, amount): if amount == 0 : return 0 if min(coins) > amount: return -1 dp = [-1 for i in range(0, amount + 1)] for i in coins: if i > len(dp) - 1: continue dp[i] = 1 for j in range(i + 1, amount + 1): if dp[j - i] == -1: continue elif dp[j] == -1: dp[j] = dp[j - i] + 1 else: dp[j] = min(dp[j], dp[j - i] + 1) #print(dp) return dp[amount] ob1 = Solution() print(ob1.coinChange([1,2,5], 11))
इनपुट
[1,2,5] 11
आउटपुट
3
