Coin change problem using dynamic programming

The coin change problem is a classic algorithmic problem in computer science and mathematics. It involves finding the number of ways to make change for a given amount of money using a set of available coin denominations. In this problem, we will explore an efficient solution using dynamic programming.

Problem Statement

Given a set of coin denominations and a target amount, the goal is to determine the number of ways to make change for the target amount using the available coins. For example, if we have coins with denominations [1, 2, 5, 7] and the target amount is 10, there are 12 possible ways to make change:

• [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
• [1, 1, 1, 1, 1, 1, 1, 1, 2]
• [1, 1, 1, 1, 1, 1, 2, 2]
• [1, 1, 1, 1, 2, 2, 2]
• [1, 1, 2, 2, 2, 2]
• [2, 2, 2, 2, 2]
• [1, 1, 1, 7]
• [1, 2, 7]
• [1, 1, 1, 1, 1, 5]
• [1, 1, 1, 2, 5]
• [1, 2, 2, 5]
• [5, 5]

Pseudocode Algorithm

To solve the coin change problem efficiently, we can use dynamic programming. Here is the pseudocode algorithm along with an explanation of each step:

function count(coins[], size, n):
if n > 0:
	collection[n + 1] // Create an array to store the collection of results
	Set the default value of collection to 0
	collection[0] = 1 // Set the first element of collection to 1

	// Iterate through each coin denomination
	for i = 0 to size:
		// Iterate through each amount from coin[i] to n
		for j = coins[i] to n:
			collection[j] += collection[j - coins[i]] // Update the collection by adding the previous solutions

	return collection[n] // Return the final result

return 0 // If no result is found
	

Code Solution

• C
• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// C program for
// Coin change problem using dynamic programming
#include <stdio.h>

int count(int coins[], int size, int n)
{
	if (n > 0)
	{
		int collection[n + 1];
		// Set default value for result collection
		for (int i = 1; i < n + 1; ++i)
		{
			collection[i] = 0;
		}
		// Set the first collection element is 1
		collection[0] = 1;
		// Execute loop through by size of coins
		for (int i = 0; i < size; i++)
		{
			// Inner loop execute in range of coins[i]..n
			for (int j = coins[i]; j <= n; j++)
			{
				collection[j] += collection[j - coins[i]];
			}
		}
		// Return calculated result
		return collection[n];
	}
	// If of no result
	return 0;
}
int main(int argc, char const *argv[])
{
	// Assume given coins is positive number
	int coins[] = {
		7 , 1 , 5 , 2
	};
	// Get the number of coins
	int size = sizeof(coins) / sizeof(coins[0]);
	int n = 10;
	/*
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	int ans = count(coins, size, n);
	printf(" Result : %d \n", ans);
	return 0;
}

 Result : 12

/*
    Java program
    Coin change problem using dynamic programming
*/
public class Counting
{
	public int count(int[] coins, int size, int n)
	{
		if (n > 0)
		{
			int[] collection = new int[n + 1];
			// Set default value for result collection
			for (int i = 1; i < n + 1; ++i)
			{
				collection[i] = 0;
			}
			// Set the first collection element is 1
			collection[0] = 1;
			// Execute loop through by size of coins
			for (int i = 0; i < size; i++)
			{
				// Inner loop execute in range of coins[i]..n
				for (int j = coins[i]; j <= n; j++)
				{
					collection[j] += collection[j - coins[i]];
				}
			}
			// Return calculated result
			return collection[n];
		}
		// If of no result
		return 0;
	}
	public static void main(String[] args)
	{
		Counting task = new Counting();
		// Assume given coins is positive number
		int[] coins = {
			7 , 1 , 5 , 2
		};
		// Get the number of coins
		int size = coins.length;
		int n = 10;
		/*
		    Target n : 10
		    ----------------
		    [1,1,1,1,1,1,1,1,1,1]
		    [1,1,1,1,1,1,1,1,2]
		    [1,1,1,1,1,1,2,2]
		    [1,1,1,1,2,2,2]
		    [1,1,2,2,2,2]
		    [2,2,2,2,2]
		    [1,1,1,7]
		    [1,2,7]
		    [1,1,1,1,1,5]
		    [1,1,1,2,5]
		    [1,2,2,5]
		    [5,5]
		    -------------------
		    12 solution
		*/
		int ans = task.count(coins, size, n);
		// Display possible result
		System.out.print(" Result : " + ans + " \n");
	}
}

 Result : 12

// Include header file
#include <iostream>

using namespace std;
/*
    C++ program
    Coin change problem using dynamic programming
*/
class Counting
{
	public: int count(int coins[], int size, int n)
	{
		if (n > 0)
		{
			int *collection = new int[n + 1];
			// Set default value for result collection
			for (int i = 1; i < n + 1; ++i)
			{
				collection[i] = 0;
			}
			// Set the first collection element is 1
			collection[0] = 1;
			// Execute loop through by size of coins
			for (int i = 0; i < size; i++)
			{
				// Inner loop execute in range of coins[i]..n
				for (int j = coins[i]; j <= n; j++)
				{
					collection[j] += collection[j - coins[i]];
				}
			}
			// Return calculated result
			return collection[n];
		}
		// If of no result
		return 0;
	}
};
int main()
{
	Counting *task = new Counting();
	// Assume given coins is positive number
	int coins[] = {
		7 , 1 , 5 , 2
	};
	// Get the number of coins
	int size = sizeof(coins) / sizeof(coins[0]);
	int n = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	int ans = task->count(coins, size, n);
	// Display possible result
	cout << " Result : " << ans << " \n";
	return 0;
}

 Result : 12

// Include namespace system
using System;
/*
    Csharp program
    Coin change problem using dynamic programming
*/
public class Counting
{
	public int count(int[] coins, int size, int n)
	{
		if (n > 0)
		{
			int[] collection = new int[n + 1];
			// Set default value for result collection
			for (int i = 1; i < n + 1; ++i)
			{
				collection[i] = 0;
			}
			// Set the first collection element is 1
			collection[0] = 1;
			// Execute loop through by size of coins
			for (int i = 0; i < size; i++)
			{
				// Inner loop execute in range of coins[i]..n
				for (int j = coins[i]; j <= n; j++)
				{
					collection[j] += collection[j - coins[i]];
				}
			}
			// Return calculated result
			return collection[n];
		}
		// If of no result
		return 0;
	}
	public static void Main(String[] args)
	{
		Counting task = new Counting();
		// Assume given coins is positive number
		int[] coins = {
			7 , 1 , 5 , 2
		};
		// Get the number of coins
		int size = coins.Length;
		int n = 10;
		/*
		    Target n : 10
		    ----------------
		    [1,1,1,1,1,1,1,1,1,1]
		    [1,1,1,1,1,1,1,1,2]
		    [1,1,1,1,1,1,2,2]
		    [1,1,1,1,2,2,2]
		    [1,1,2,2,2,2]
		    [2,2,2,2,2]
		    [1,1,1,7]
		    [1,2,7]
		    [1,1,1,1,1,5]
		    [1,1,1,2,5]
		    [1,2,2,5]
		    [5,5]
		    -------------------
		    12 solution
		*/
		int ans = task.count(coins, size, n);
		// Display possible result
		Console.Write(" Result : " + ans + " \n");
	}
}

 Result : 12

package main
import "fmt"
/*
    Go program
    Coin change problem using dynamic programming
*/

func count(coins[] int, size int, n int) int {
	if n > 0 {
		var collection = make([]int,n+1)
		// Set the first collection element is 1
		collection[0] = 1
		// Execute loop through by size of coins
		for i := 0 ; i < size ; i++ {
			// Inner loop execute in range of coins[i]..n
			for j := coins[i] ; j <= n ; j++ {
				collection[j] += collection[j - coins[i]]
			}
		}
		// Return calculated result
		return collection[n]
	}
	// If of no result
	return 0
}
func main() {
	// Assume given coins is positive number
	var coins = [] int {
		7,
		1,
		5,
		2,
	}
	// Get the number of coins
	var size int = len(coins)
	var n int = 10
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	var ans int = count(coins, size, n)
	// Display possible result
	fmt.Print(" Result : ", ans, " \n")
}

 Result : 12

<?php
/*
    Php program
    Coin change problem using dynamic programming
*/
class Counting
{
	public	function count($coins, $size, $n)
	{
		if ($n > 0)
		{
			$collection = array_fill(0, $n + 1, 0);
			// Set the first collection element is 1
			$collection[0] = 1;
			// Execute loop through by size of coins
			for ($i = 0; $i < $size; $i++)
			{
				// Inner loop execute in range of coins[i]..n
				for ($j = $coins[$i]; $j <= $n; $j++)
				{
					$collection[$j] += $collection[$j - $coins[$i]];
				}
			}
			// Return calculated result
			return $collection[$n];
		}
		// If of no result
		return 0;
	}
}

function main()
{
	$task = new Counting();
	// Assume given coins is positive number
	$coins = array(7, 1, 5, 2);
	// Get the number of coins
	$size = count($coins);
	$n = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	$ans = $task->count($coins, $size, $n);
	// Display possible result
	echo(" Result : ".$ans." \n");
}
main();

 Result : 12

/*
    Node JS program
    Coin change problem using dynamic programming
*/
class Counting
{
	count(coins, size, n)
	{
		if (n > 0)
		{
			var collection = Array(n + 1).fill(0);
			// Set the first collection element is 1
			collection[0] = 1;
			// Execute loop through by size of coins
			for (var i = 0; i < size; i++)
			{
				// Inner loop execute in range of coins[i]..n
				for (var j = coins[i]; j <= n; j++)
				{
					collection[j] += collection[j - coins[i]];
				}
			}
			// Return calculated result
			return collection[n];
		}
		// If of no result
		return 0;
	}
}

function main()
{
	var task = new Counting();
	// Assume given coins is positive number
	var coins = [7, 1, 5, 2];
	// Get the number of coins
	var size = coins.length;
	var n = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	var ans = task.count(coins, size, n);
	// Display possible result
	process.stdout.write(" Result : " + ans + " \n");
}
main();

 Result : 12

#    Python 3 program
#    Coin change problem using dynamic programming
class Counting :
	def count(self, coins, size, n) :
		if (n > 0) :
			collection = [0] * (n + 1)
			#  Set the first collection element is 1
			collection[0] = 1
			i = 0
			#  Execute loop through by size of coins
			while (i < size) :
				j = coins[i]
				#  Inner loop execute in range of coins[i]..n
				while (j <= n) :
					collection[j] += collection[j - coins[i]]
					j += 1
				
				i += 1
			
			#  Return calculated result
			return collection[n]
		
		#  If of no result
		return 0
	

def main() :
	task = Counting()
	#  Assume given coins is positive number
	coins = [7, 1, 5, 2]
	#  Get the number of coins
	size = len(coins)
	n = 10
	#    Target n : 10
	#    ----------------
	#    [1,1,1,1,1,1,1,1,1,1]
	#    [1,1,1,1,1,1,1,1,2]
	#    [1,1,1,1,1,1,2,2]
	#    [1,1,1,1,2,2,2]
	#    [1,1,2,2,2,2]
	#    [2,2,2,2,2]
	#    [1,1,1,7]
	#    [1,2,7]
	#    [1,1,1,1,1,5]
	#    [1,1,1,2,5]
	#    [1,2,2,5]
	#    [5,5]
	#    -------------------
	#    12 solution
	ans = task.count(coins, size, n)
	#  Display possible result
	print(" Result : ", ans ," ")

if __name__ == "__main__": main()

 Result :  12

#    Ruby program
#    Coin change problem using dynamic programming
class Counting 
	def count(coins, size, n) 
		if (n > 0) 
			collection = Array.new(n + 1) {0}
			#  Set the first collection element is 1
			collection[0] = 1
			i = 0
			#  Execute loop through by size of coins
			while (i < size) 
				j = coins[i]
				#  Inner loop execute in range of coins[i]..n
				while (j <= n) 
					collection[j] += collection[j - coins[i]]
					j += 1
				end

				i += 1
			end

			#  Return calculated result
			return collection[n]
		end

		#  If of no result
		return 0
	end

end

def main() 
	task = Counting.new()
	#  Assume given coins is positive number
	coins = [7, 1, 5, 2]
	#  Get the number of coins
	size = coins.length
	n = 10
	#    Target n : 10
	#    ----------------
	#    [1,1,1,1,1,1,1,1,1,1]
	#    [1,1,1,1,1,1,1,1,2]
	#    [1,1,1,1,1,1,2,2]
	#    [1,1,1,1,2,2,2]
	#    [1,1,2,2,2,2]
	#    [2,2,2,2,2]
	#    [1,1,1,7]
	#    [1,2,7]
	#    [1,1,1,1,1,5]
	#    [1,1,1,2,5]
	#    [1,2,2,5]
	#    [5,5]
	#    -------------------
	#    12 solution
	ans = task.count(coins, size, n)
	#  Display possible result
	print(" Result : ", ans ," \n")
end

main()

 Result : 12 

/*
    Scala program
    Coin change problem using dynamic programming
*/
class Counting()
{
	def count(coins: Array[Int], size: Int, n: Int): Int = {
		if (n > 0)
		{
			var collection: Array[Int] = Array.fill[Int](n + 1)(0);
			// Set the first collection element is 1
			collection(0) = 1;
			var i: Int = 0;
			// Execute loop through by size of coins
			while (i < size)
			{
				var j: Int = coins(i);
				// Inner loop execute in range of coins[i]..n
				while (j <= n)
				{
					collection(j) += collection(j - coins(i));
					j += 1;
				}
				i += 1;
			}
			// Return calculated result
			return collection(n);
		}
		// If of no result
		return 0;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Counting = new Counting();
		// Assume given coins is positive number
		var coins: Array[Int] = Array(7, 1, 5, 2);
		// Get the number of coins
		var size: Int = coins.length;
		var n: Int = 10;
		/*
		    Target n : 10
		    ----------------
		    [1,1,1,1,1,1,1,1,1,1]
		    [1,1,1,1,1,1,1,1,2]
		    [1,1,1,1,1,1,2,2]
		    [1,1,1,1,2,2,2]
		    [1,1,2,2,2,2]
		    [2,2,2,2,2]
		    [1,1,1,7]
		    [1,2,7]
		    [1,1,1,1,1,5]
		    [1,1,1,2,5]
		    [1,2,2,5]
		    [5,5]
		    -------------------
		    12 solution
		*/
		var ans: Int = task.count(coins, size, n);
		// Display possible result
		print(" Result : " + ans + " \n");
	}
}

 Result : 12

import Foundation;
/*
    Swift 4 program
    Coin change problem using dynamic programming
*/
class Counting
{
	func count(_ coins: [Int], _ size: Int, _ n: Int) -> Int
	{
		if (n > 0)
		{
			var collection: [Int] = Array(repeating: 0, count: n + 1);
			// Set the first collection element is 1
			collection[0] = 1;
			var i: Int = 0;
			// Execute loop through by size of coins
			while (i < size)
			{
				var j: Int = coins[i];
				// Inner loop execute in range of coins[i]..n
				while (j <= n)
				{
					collection[j] += collection[j - coins[i]];
					j += 1;
				}
				i += 1;
			}
			// Return calculated result
			return collection[n];
		}
		// If of no result
		return 0;
	}
}
func main()
{
	let task: Counting = Counting();
	// Assume given coins is positive number
	let coins: [Int] = [7, 1, 5, 2];
	// Get the number of coins
	let size: Int = coins.count;
	let n: Int = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	let ans: Int = task.count(coins, size, n);
	// Display possible result
	print(" Result : ", ans ," ");
}
main();

 Result :  12

/*
    Kotlin program
    Coin change problem using dynamic programming
*/
class Counting
{
	fun count(coins: Array < Int > , size: Int, n: Int): Int
	{
		if (n > 0)
		{
			var collection: Array < Int > = Array(n + 1)
			{
				0
			};
			// Set the first collection element is 1
			collection[0] = 1;
			var i: Int = 0;
			// Execute loop through by size of coins
			while (i < size)
			{
				var j: Int = coins[i];
				// Inner loop execute in range of coins[i]..n
				while (j <= n)
				{
					collection[j] += collection[j - coins[i]];
					j += 1;
				}
				i += 1;
			}
			// Return calculated result
			return collection[n];
		}
		// If of no result
		return 0;
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Counting = Counting();
	// Assume given coins is positive number
	val coins: Array < Int > = arrayOf(7, 1, 5, 2);
	// Get the number of coins
	val size: Int = coins.count();
	val n: Int = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	val ans: Int = task.count(coins, size, n);
	// Display possible result
	print(" Result : " + ans + " \n");
}

 Result : 12

Explanation

The algorithm starts by initializing an array called "collection" with size n + 1. This array will store the number of ways to make change for each amount from 0 to n. The default value for all elements in the collection is set to 0, except for the first element, which is set to 1 since there is one way to make change for an amount of 0 (by not selecting any coin).

The algorithm then iterates through each coin denomination. For each denomination, it iterates through each amount from the current coin value to the target amount n. It updates the collection by adding the number of ways to make change for the current amount minus the current coin value (collection[j - coins[i]]) to the current number of ways to make change (collection[j]). This step ensures that we consider all possible combinations of coins to make change for the current amount.

Finally, the algorithm returns the value stored in the collection at index n, which represents the total number of ways to make change for the target amount.

In the given example, the algorithm is executed with coins = [7, 1, 5, 2] and n = 10. The resulting output is 12, indicating that there are 12 different ways to make change for 10 using the given coins.

Time Complexity

The time complexity of the dynamic programming solution for the coin change problem is O(size * n), where "size" is the number of coin denominations and "n" is the target amount. This is because we iterate through each coin denomination for each amount from 0 to n. Therefore, the algorithm has a linear time complexity relative to the input size.

Conclusion

The coin change problem can be efficiently solved using dynamic programming. By breaking down the problem into smaller subproblems and using the results of the subproblems to build the final solution, we can determine the number of ways to make change for a target amount using a given set of coin denominations. The algorithm has a linear time complexity, making it an effective solution for larger inputs.