Skip to main content

Coin change problem using dynamic programming

Here given code implementation process.

// 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;
}

input

 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");
	}
}

input

 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;
}

input

 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");
	}
}

input

 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")
}

input

 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();

input

 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();

input

 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()

input

 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()

input

 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");
	}
}

input

 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();

input

 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");
}

input

 Result : 12




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment