Coin Change समस्या

Coin change अपने पास मौजूद coins से कम से कम possible coins में candy के लिए पैसे देने जैसा है।

In this page:

Problem Idea
DP State
Transition
Ways to Make Change
Practice

Syntax

markup

dp = [float('inf')] * (amount + 1)
dp[0] = 0
for x in range(1, amount + 1):
    for coin in coins:
        if coin <= x:
            dp[x] = min(dp[x], dp[x - coin] + 1)

Problem Idea

Coin change का classic version दिए गए denominations के एक set से minimum coins मांगता है जो बिल्कुल एक target amount तक add हों, या report करता है कि यह impossible है अगर कोई combination काम न करे।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int coins[] = {1, 3, 4}, amount = 6;
	cout << "Fewest coins from {1,3,4} to make " << amount << ", or -1 if impossible";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] coins = {1, 3, 4};
		int amount = 6;
		System.out.println("Fewest coins from {1,3,4} to make " + amount + ", or -1 if impossible");
	}
}

coins, amount = [1, 3, 4], 6
print(f"Fewest coins from {{1,3,4}} to make {amount}, or -1 if impossible")

#include <stdio.h>
int main() {
	int coins[] = {1, 3, 4}, amount = 6;
	printf("Fewest coins from {1,3,4} to make %d, or -1 if impossible", amount);
	return 0;
}

DP State

dp[x] amount x बनाने के लिए चाहिए सबसे कम coins store करता है, dp[0] = 0 (zero amount के लिए zero coins) से बनाया गया ताकि हर बड़ा amount पहले से solved छोटे वालों से compute हो सके।

उदाहरण: DP State

#include <iostream>
using namespace std;
int main() {
	int dp[7]; dp[0] = 0;
	cout << "dp[0] = 0 coins for amount 0; every dp[x] for x>0 built from smaller amounts already solved";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] dp = new int[7]; dp[0] = 0;
		System.out.println("dp[0] = 0 coins for amount 0; every dp[x] for x>0 built from smaller amounts already solved");
	}
}

dp = [0] * 7
print("dp[0] = 0 coins for amount 0; every dp[x] for x>0 built from smaller amounts already solved")

#include <stdio.h>
int main() {
	int dp[7] = {0};
	printf("dp[0] = 0 coins for amount 0; every dp[x] for x>0 built from smaller amounts already solved");
	return 0;
}

Transition

हर coin denomination के लिए जो amount x में fit होने लायक छोटी हो, एक option उस coin plus बचे amount (x माइनस coin की value) के लिए चाहिए कितने भी coins उपयोग करना है — dp[x] फिट होने वाले हर coin में minimum लेता है।

उदाहरण: Transition

#include <iostream>
using namespace std;
int main() {
	int coins[] = {1,3,4}, amount = 6;
	int dp[7]; dp[0] = 0;
	for (int x = 1; x <= amount; x++) {
		dp[x] = 1000000;
		for (int c : coins) if (c <= x) dp[x] = min(dp[x], dp[x-c] + 1);
	}
	cout << "Fewest coins for " << amount << ": " << dp[amount];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] coins = {1,3,4};
		int amount = 6;
		int[] dp = new int[7]; dp[0] = 0;
		for (int x = 1; x <= amount; x++) {
			dp[x] = 1000000;
			for (int c : coins) if (c <= x) dp[x] = Math.min(dp[x], dp[x-c] + 1);
		}
		System.out.println("Fewest coins for " + amount + ": " + dp[amount]);
	}
}

coins, amount = [1,3,4], 6
dp = [0] + [float('inf')] * amount
for x in range(1, amount+1):
    for c in coins:
        if c <= x:
            dp[x] = min(dp[x], dp[x-c] + 1)
print("Fewest coins for", amount, ":", dp[amount])

#include <stdio.h>
int main() {
	int coins[] = {1,3,4}, amount = 6;
	int dp[7]; dp[0] = 0;
	for (int x = 1; x <= amount; x++) {
		dp[x] = 1000000;
		for (int i = 0; i < 3; i++) if (coins[i] <= x && dp[x-coins[i]]+1 < dp[x]) dp[x] = dp[x-coins[i]]+1;
	}
	printf("Fewest coins for %d: %d", amount, dp[amount]);
	return 0;
}

Ways to Make Change

एक closely related लेकिन अलग सवाल पूछता है कि target amount बनाने के लिए coins के कितने distinct combinations हो सकते हैं, सबसे कम coins के बजाय — वह variant वही table shape उपयोग करता है लेकिन minimize करने के बजाय possibilities count (sums) करता है।

उदाहरण: Ways to Make Change

#include <iostream>
using namespace std;
int main() {
	int coins[] = {1,2,5}, amount = 5;
	int dp[6] = {0}; dp[0] = 1;
	for (int c : coins)
		for (int x = c; x <= amount; x++) dp[x] += dp[x-c];
	cout << "Distinct combinations to make " << amount << ": " << dp[amount];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] coins = {1,2,5};
		int amount = 5;
		int[] dp = new int[6]; dp[0] = 1;
		for (int c : coins)
			for (int x = c; x <= amount; x++) dp[x] += dp[x-c];
		System.out.println("Distinct combinations to make " + amount + ": " + dp[amount]);
	}
}

coins, amount = [1,2,5], 5
dp = [0]*(amount+1)
dp[0] = 1
for c in coins:
    for x in range(c, amount+1):
        dp[x] += dp[x-c]
print("Distinct combinations to make", amount, ":", dp[amount])

#include <stdio.h>
int main() {
	int coins[] = {1,2,5}, amount = 5;
	int dp[6] = {0}; dp[0] = 1;
	for (int i = 0; i < 3; i++)
		for (int x = coins[i]; x <= amount; x++) dp[x] += dp[x-coins[i]];
	printf("Distinct combinations to make %d: %d", amount, dp[amount]);
	return 0;
}

Practice

चूंकि किसी भी denomination को ज़रूरत के अनुसार कितनी भी बार reuse किया जा सकता है, coin change एक cash register पर change बनाने पर apply unbounded knapsack pattern का एक direct real-world example है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Coin change is unbounded knapsack applied directly to making change at a cash register";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Coin change is unbounded knapsack applied directly to making change at a cash register");
	}
}

print("Coin change is unbounded knapsack applied directly to making change at a cash register")

#include <stdio.h>
int main() {
	printf("Coin change is unbounded knapsack applied directly to making change at a cash register");
	return 0;
}

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson Edit Distance Next Lesson → Matrix Chain Multiplication