# 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)
{
// 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()
{
// 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)
{
// 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()
{
// 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
*/
// 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()
{
// 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() :
#  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
#  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()
#  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
#  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()
{
// 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
{
// 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.