Cambio de moneda | DP-7

 

Dado un valor N, si queremos dar cambio por N centavos, y tenemos un suministro infinito de cada una de las monedas valoradas en S = { S1, S2, .. , Sm}, ¿de cuántas formas podemos hacer el cambio? El orden de las monedas no importa.
Por ejemplo, para N = 4 y S = {1,2,3}, hay cuatro soluciones: {1,1,1,1},{1,1,2},{2,2},{1, 3}. Entonces, la salida debería ser 4. Para N = 10 y S = {2, 5, 3, 6}, hay cinco soluciones: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} y {5,5}. Entonces la salida debería ser 5.

1) Subestructura óptima 
Para contar el número total de soluciones, podemos dividir todas las soluciones del conjunto en dos conjuntos. 
1) Soluciones que no contienen moneda mth (o Sm). 
2) Soluciones que contengan al menos un Sm. 
Sea count(S[], m, n) la función para contar el número de soluciones, entonces se puede escribir como la suma de count(S[], m-1, n) y count(S[], m, n-Sm).
Por lo tanto, el problema tiene una propiedad de subestructura óptima ya que el problema se puede resolver usando soluciones a los subproblemas. 

2) Subproblemas superpuestos A 
continuación se muestra una implementación recursiva simple del problema de cambio de moneda. La implementación simplemente sigue la estructura recursiva mencionada anteriormente.

3) Enfoque (Algoritmo)

Mira, aquí cada moneda de una denominación dada puede venir un número infinito de veces. (Se permite la repetición), esto es lo que llamamos MOCHILA SIN LÍMITES. Tenemos 2 opciones para una moneda de una denominación particular, ya sea i) para incluir, o ii) para excluir. Pero aquí, el proceso de inclusión no es de una sola vez; podemos incluir cualquier denominación cualquier número de veces hasta N<0.

Básicamente, si estamos en s[m-1], podemos tomar tantas instancias de esa moneda (inclusión ilimitada), es decir , count(S, m, n – S[m-1]) ; luego pasamos a s[m-2]. Después de pasar a s[m-2], no podemos retroceder y no podemos tomar decisiones para s[m-1], es decir , count(S, m-1, n) .

Finalmente, como tenemos que encontrar el número total de formas, sumaremos estas 2 opciones posibles, es decir, count(S, m, n – S[m-1] ) + count(S, m-1, n ) ; que será nuestra respuesta requerida.

C++

// Recursive C++ program for
// coin change problem.
#include <bits/stdc++.h>
using namespace std;
 
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
int count(int S[], int m, int n)
{
     
    // If n is 0 then there is 1 solution
    // (do not include any coin)
    if (n == 0)
        return 1;
     
    // If n is less than 0 then no
    // solution exists
    if (n < 0)
        return 0;
 
    // If there are no coins and n
    // is greater than 0, then no
    // solution exist
    if (m <= 0)
        return 0;
 
    // count is sum of solutions (i)
    // including S[m-1] (ii) excluding S[m-1]
    return count(S, m - 1, n) +
           count(S, m, n - S[m - 1]);
}
 
// Driver code
int main()
{
    int i, j;
    int arr[] = { 1, 2, 3 };
    int m = sizeof(arr) / sizeof(arr[0]);
     
    cout << " " << count(arr, m, 4);
     
    return 0;
}
 
// This code is contributed by shivanisinghss2110

C

// Recursive C program for
// coin change problem.
#include<stdio.h>
 
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
int count( int S[], int m, int n )
{
    // If n is 0 then there is 1 solution
    // (do not include any coin)
    if (n == 0)
        return 1;
     
    // If n is less than 0 then no
    // solution exists
    if (n < 0)
        return 0;
 
    // If there are no coins and n
    // is greater than 0, then no
    // solution exist
    if (m <=0)
        return 0;
 
    // count is sum of solutions (i)
    // including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
 
// Driver program to test above function
int main()
{
    int i, j;
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 4));
    getchar();
    return 0;
}

Java

// Recursive JAVA program for
// coin change problem.
import java.util.*;
class GFG
{
 
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
static int count(int S[], int m, int n)
{
     
    // If n is 0 then there is 1 solution
    // (do not include any coin)
    if (n == 0)
        return 1;
     
    // If n is less than 0 then no
    // solution exists
    if (n < 0)
        return 0;
 
    // If there are no coins and n
    // is greater than 0, then no
    // solution exist
    if (m <= 0)
        return 0;
 
    // count is sum of solutions (i)
    // including S[m-1] (ii) excluding S[m-1]
    return count(S, m - 1, n) +
           count(S, m, n - S[m - 1]);
}
 
// Driver code
public static void  main(String args[])
{
    int arr[] = { 1, 2, 3 };
    int m = arr.length;
     
    System.out.println(count(arr, m, 4));
}
 
}
 
// This code is contributed by jyoti369

Python3

# Recursive Python3 program for
# coin change problem.
 
# Returns the count of ways we can sum
# S[0...m-1] coins to get sum n
def count(S, m, n ):
 
    # If n is 0 then there is 1
    # solution (do not include any coin)
    if (n == 0):
        return 1
 
    # If n is less than 0 then no
    # solution exists
    if (n < 0):
        return 0;
 
    # If there are no coins and n
    # is greater than 0, then no
    # solution exist
    if (m <=0):
        return 0
 
    # count is sum of solutions (i)
    # including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
 
# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
print(count(arr, m, 4))
 
# This code is contributed by Smitha Dinesh Semwal

C#

// Recursive C# program for
// coin change problem.
using System;
 
class GFG
{
    // Returns the count of ways we can
    // sum S[0...m-1] coins to get sum n
    static int count( int []S, int m, int n )
    {
        // If n is 0 then there is 1 solution
        // (do not include any coin)
        if (n == 0)
            return 1;
         
        // If n is less than 0 then no
        // solution exists
        if (n < 0)
            return 0;
     
        // If there are no coins and n
        // is greater than 0, then no
        // solution exist
        if (m <=0)
            return 0;
     
        // count is sum of solutions (i)
        // including S[m-1] (ii) excluding S[m-1]
        return count( S, m - 1, n ) +
            count( S, m, n - S[m - 1] );
    }
     
    // Driver program
    public static void Main()
    {
         
        int []arr = {1, 2, 3};
        int m = arr.Length;
        Console.Write( count(arr, m, 4));
         
         
    }
}
// This code is contributed by Sam007

PHP

<?php
// Recursive PHP program for
// coin change problem.
 
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
function coun($S, $m, $n)
{
     
    // If n is 0 then there is
    // 1 solution (do not include
    // any coin)
    if ($n == 0)
        return 1;
     
    // If n is less than 0 then no
    // solution exists
    if ($n < 0)
        return 0;
 
    // If there are no coins and n
    // is greater than 0, then no
    // solution exist
    if ($m <= 0)
        return 0;
 
    // count is sum of solutions (i)
    // including S[m-1] (ii) excluding S[m-1]
    return coun($S, $m - 1,$n ) +
           coun($S, $m, $n - $S[$m - 1] );
}
 
    // Driver Code
    $arr = array(1, 2, 3);
    $m = count($arr);
    echo coun($arr, $m, 4);
     
// This code is contributed by Sam007
?>

Javascript

<script>
// Recursive javascript program for
// coin change problem.
    
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
function count(S , m , n )
{
 
    // If n is 0 then there is 1 solution
    // (do not include any coin)
    if (n == 0)
        return 1;
     
    // If n is less than 0 then no
    // solution exists
    if (n < 0)
        return 0;
 
    // If there are no coins and n
    // is greater than 0, then no
    // solution exist
    if (m <=0)
        return 0;
 
    // count is sum of solutions (i)
    // including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) +
           count( S, m, n - S[m - 1] );
}
 
// Driver program to test above function
var arr = [1, 2, 3];
var m = arr.length;
document.write( count(arr, m, 4));
 
// This code is contributed by Amit Katiyar
</script>
Producción

 4

Complejidad del tiempo: O(2 n )

Complejidad espacial: O (objetivo): espacio de pila auxiliar

Cabe señalar que la función anterior calcula los mismos subproblemas una y otra vez. Vea el siguiente árbol de recursión para S = {1, 2, 3} y n = 5. 

La función C({1}, 3) se llama dos veces. Si dibujamos el árbol completo, podemos ver que hay muchos subproblemas que se llaman más de una vez.  

C() --> count()
                             C({1,2,3}, 5)                     
                           /             \    
                         /                 \                  
             C({1,2,3}, 2)                 C({1,2}, 5)
            /       \                      /      \         
           /         \                    /         \   
C({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)
               /    \             /     \           /     \
             /       \           /       \         /        \
    C({1,2},0)  C({1},2)   C({1,2},1) C({1},3)    C({1}, 4)  C({}, 5)
                   / \     / \        /\         /     \         
                  /   \   /   \     /   \       /       \  
                .      .  .     .   .     .   C({1}, 3) C({}, 4)
                                               / \ 
                                              /   \   
                                             .      .

Dado que los mismos subproblemas se vuelven a llamar, este problema tiene la propiedad Superposición de subproblemas. Entonces, el problema de cambio de monedas tiene las dos propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica (DP) , los cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una tabla de array temporal [] [] de forma ascendente.

Solución de programación dinámica  

C++

// C++ program for coin change problem.
#include<bits/stdc++.h>
 
using namespace std;
 
int count( int S[], int m, int n )
{
    int i, j, x, y;
 
    // We need n+1 rows as the table
    // is constructed in bottom up
    // manner using the base case 0
    // value case (n = 0)
    int table[n + 1][m];
     
    // Fill the entries for 0
    // value case (n = 0)
    for (i = 0; i < m; i++)
        table[0][i] = 1;
 
    // Fill rest of the table entries
    // in bottom up manner
    for (i = 1; i < n + 1; i++)
    {
        for (j = 0; j < m; j++)
        {
            // Count of solutions including S[j]
            x = (i-S[j] >= 0) ? table[i - S[j]][j] : 0;
 
            // Count of solutions excluding S[j]
            y = (j >= 1) ? table[i][j - 1] : 0;
 
            // total count
            table[i][j] = x + y;
        }
    }
    return table[n][m - 1];
}
 
// Driver Code
int main()
{
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    cout << count(arr, m, n);
    return 0;
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

C

// C program for coin change problem.
#include<stdio.h>
 
int count( int S[], int m, int n )
{
    int i, j, x, y;
 
    // We need n+1 rows as the table is constructed
    // in bottom up manner using the base case 0
    // value case (n = 0)
    int table[n+1][m];
    
    // Fill the entries for 0 value case (n = 0)
    for (i=0; i<m; i++)
        table[0][i] = 1;
 
    // Fill rest of the table entries in bottom
    // up manner 
    for (i = 1; i < n+1; i++)
    {
        for (j = 0; j < m; j++)
        {
            // Count of solutions including S[j]
            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
 
            // Count of solutions excluding S[j]
            y = (j >= 1)? table[i][j-1]: 0;
 
            // total count
            table[i][j] = x + y;
        }
    }
    return table[n][m-1];
}
 
// Driver program to test above function
int main()
{
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    printf(" %d ", count(arr, m, n));
    return 0;
}

Java

/* Dynamic Programming Java implementation of Coin
   Change problem */
import java.util.Arrays;
 
class CoinChange
{
    static long countWays(int S[], int m, int n)
    {
        //Time complexity of this function: O(mn)
        //Space Complexity of this function: O(n)
 
        // table[i] will be storing the number of solutions
        // for value i. We need n+1 rows as the table is
        // constructed in bottom up manner using the base
        // case (n = 0)
        long[] table = new long[n+1];
 
        // Initialize all table values as 0
        Arrays.fill(table, 0);   //O(n)
 
        // Base case (If given value is 0)
        table[0] = 1;
 
        // Pick all coins one by one and update the table[]
        // values after the index greater than or equal to
        // the value of the picked coin
        for (int i=0; i<m; i++)
            for (int j=S[i]; j<=n; j++)
                table[j] += table[j-S[i]];
 
        return table[n];
    }
 
    // Driver Function to test above function
    public static void main(String args[])
    {
        int arr[] = {1, 2, 3};
        int m = arr.length;
        int n = 4;
        System.out.println(countWays(arr, m, n));
    }
}
// This code is contributed by Pankaj Kumar

Python

# Dynamic Programming Python implementation of Coin
# Change problem
def count(S, m, n):
    # We need n+1 rows as the table is constructed
    # in bottom up manner using the base case 0 value
    # case (n = 0)
    table = [[0 for x in range(m)] for x in range(n+1)]
 
    # Fill the entries for 0 value case (n = 0)
    for i in range(m):
        table[0][i] = 1
 
    # Fill rest of the table entries in bottom up manner
    for i in range(1, n+1):
        for j in range(m):
 
            # Count of solutions including S[j]
            x = table[i - S[j]][j] if i-S[j] >= 0 else 0
 
            # Count of solutions excluding S[j]
            y = table[i][j-1] if j >= 1 else 0
 
            # total count
            table[i][j] = x + y
 
    return table[n][m-1]
 
# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
n = 4
print(count(arr, m, n))
 
# This code is contributed by Bhavya Jain

C#

/* Dynamic Programming C# implementation of Coin
Change problem */
using System;
 
class GFG
{
    static long countWays(int []S, int m, int n)
    {
        //Time complexity of this function: O(mn)
        //Space Complexity of this function: O(n)
 
        // table[i] will be storing the number of solutions
        // for value i. We need n+1 rows as the table is
        // constructed in bottom up manner using the base
        // case (n = 0)
        int[] table = new int[n+1];
 
        // Initialize all table values as 0
        for(int i = 0; i < table.Length; i++)
        {
            table[i] = 0;
        }
 
        // Base case (If given value is 0)
        table[0] = 1;
 
        // Pick all coins one by one and update the table[]
        // values after the index greater than or equal to
        // the value of the picked coin
        for (int i = 0; i < m; i++)
            for (int j = S[i]; j <= n; j++)
                table[j] += table[j - S[i]];
 
        return table[n];
    }
 
    // Driver Function
    public static void Main()
    {
        int []arr = {1, 2, 3};
        int m = arr.Length;
        int n = 4;
        Console.Write(countWays(arr, m, n));
    }
}
// This code is contributed by Sam007

PHP

<?php
// PHP program for
// coin change problem.
 
function count1($S, $m, $n)
{
    // We need n+1 rows as
    // the table is constructed
    // in bottom up manner
    // using the base case 0
    // value case (n = 0)
    $table;
    for ($i = 0; $i < $n + 1; $i++)
    for ($j = 0; $j < $m; $j++)
        $table[$i][$j] = 0;
     
    // Fill the entries for
    // 0 value case (n = 0)
    for ($i = 0; $i < $m; $i++)
        $table[0][$i] = 1;
 
    // Fill rest of the table
    // entries in bottom up manner
    for ($i = 1; $i < $n + 1; $i++)
    {
        for ($j = 0; $j < $m; $j++)
        {
            // Count of solutions
            // including S[j]
            $x = ($i-$S[$j] >= 0) ?
                  $table[$i - $S[$j]][$j] : 0;
 
            // Count of solutions
            // excluding S[j]
            $y = ($j >= 1) ?
                  $table[$i][$j - 1] : 0;
 
            // total count
            $table[$i][$j] = $x + $y;
        }
    }
    return $table[$n][$m-1];
}
 
// Driver Code
$arr = array(1, 2, 3);
$m = count($arr);
$n = 4;
echo count1($arr, $m, $n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
/* Dynamic Programming javascript implementation of Coin
   Change problem */
 
function countWays(S , m , n)
{
    //Time complexity of this function: O(mn)
    //Space Complexity of this function: O(n)
 
    // table[i] will be storing the number of solutions
    // for value i. We need n+1 rows as the table is
    // constructed in bottom up manner using the base
    // case (n = 0)
    // Initialize all table values as 0
    //O(n)
    var table = Array(n+1).fill(0);
     
 
    // Base case (If given value is 0)
    table[0] = 1;
 
    // Pick all coins one by one and update the table
    // values after the index greater than or equal to
    // the value of the picked coin
    for (i=0; i<m; i++)
        for (j=S[i]; j<=n; j++)
            table[j] += table[j-S[i]];
 
    return table[n];
}
 
// Driver Function to test above function
var arr = [1, 2, 3];
var m = arr.length;
var n = 4;
document.write(countWays(arr, m, n));
 
// This code is contributed by 29AjayKumar
 
</script>
Producción

4

Complejidad de tiempo: O(mn) 
La siguiente es una versión simplificada del método 2. El espacio auxiliar requerido aquí es O(n) solamente. 

C++

int count( int S[], int m, int n )         
{         
 // table[i] will be storing the number of solutions for         
 // value i. We need n+1 rows as the table is constructed         
 // in bottom up manner using the base case (n = 0)         
 int table[n+1];         
 // Initialize all table values as 0         
 memset(table, 0, sizeof(table));         
 // Base case (If given value is 0)         
 table[0] = 1;         
 // Pick all coins one by one and update the table[] values         
 // after the index greater than or equal to the value of the         
 // picked coin         
 for(int i=0; i<m; i++)         
 for(int j=S[i]; j<=n; j++)         
 table[j] += table[j-S[i]];         
 return table[n];         
}         

Java

public static int count( int S[], int m, int n )
{
    // table[i] will be storing the number of solutions for
    // value i. We need n+1 rows as the table is constructed
    // in bottom up manner using the base case (n = 0)
    int table[]=new int[n+1];
 
    // Base case (If given value is 0)
    table[0] = 1;
 
    // Pick all coins one by one and update the table[] values
    // after the index greater than or equal to the value of the
    // picked coin
    for(int i=0; i<m; i++)
        for(int j=S[i]; j<=n; j++)
            table[j] += table[j-S[i]];
 
    return table[n];
}

Python

# Dynamic Programming Python implementation of Coin
# Change problem
def count(S, m, n):
 
    # table[i] will be storing the number of solutions for
    # value i. We need n+1 rows as the table is constructed
    # in bottom up manner using the base case (n = 0)
    # Initialize all table values as 0
    table = [0 for k in range(n+1)]
 
    # Base case (If given value is 0)
    table[0] = 1
 
    # Pick all coins one by one and update the table[] values
    # after the index greater than or equal to the value of the
    # picked coin
    for i in range(0,m):
        for j in range(S[i],n+1):
            table[j] += table[j-S[i]]
 
    return table[n]
 
# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
n = 4
x = count(arr, m, n)
print (x)
 
# This code is contributed by Afzal Ansari

C#

// Dynamic Programming C# implementation
// of Coin Change problem
using System;
 
class GFG
{
static int count(int []S, int m, int n)
{
    // table[i] will be storing the
    // number of solutions for value i.
    // We need n+1 rows as the table
    // is constructed in bottom up manner
    // using the base case (n = 0)
    int [] table = new int[n + 1];
     
    // Base case (If given value is 0)
    table[0] = 1;
 
    // Pick all coins one by one and
    // update the table[] values after
    // the index greater than or equal
    // to the value of the picked coin
    for(int i = 0; i < m; i++)
        for(int j = S[i]; j <= n; j++)
            table[j] += table[j - S[i]];
 
    return table[n];
}
 
// Driver Code
public static void Main()
{
    int []arr = {1, 2, 3};
    int m = arr.Length;
    int n = 4;
    Console.Write(count(arr, m, n));
}
}
 
// This code is contributed by Raj

PHP

<?php
function count_1( &$S, $m, $n )
{
    // table[i] will be storing the number
    // of solutions for value i. We need n+1
    // rows as the table is constructed in
    // bottom up manner using the base case (n = 0)
    $table = array_fill(0, $n + 1, NULl);
 
    // Base case (If given value is 0)
    $table[0] = 1;
 
    // Pick all coins one by one and update
    // the table[] values after the index
    // greater than or equal to the value
    // of the picked coin
    for($i = 0; $i < $m; $i++)
        for($j = $S[$i]; $j <= $n; $j++)
            $table[$j] += $table[$j - $S[$i]];
 
    return $table[$n];
}
 
// Driver Code
$arr = array(1, 2, 3);
$m = sizeof($arr);
$n = 4;
$x = count_1($arr, $m, $n);
echo $x;
 
// This code is contributed
// by ChitraNayal
?>

Javascript

<script>
    // Dynamic Programming Javascript implementation
    // of Coin Change problem
       
    function count(S, m, n)
    {
        // table[i] will be storing the
        // number of solutions for value i.
        // We need n+1 rows as the table
        // is constructed in bottom up manner
        // using the base case (n = 0)
        let table = new Array(n + 1);
        table.fill(0);
 
        // Base case (If given value is 0)
        table[0] = 1;
 
        // Pick all coins one by one and
        // update the table[] values after
        // the index greater than or equal
        // to the value of the picked coin
        for(let i = 0; i < m; i++)
            for(let j = S[i]; j <= n; j++)
                table[j] += table[j - S[i]];
 
        return table[n];
    }
     
    let arr = [1, 2, 3];
    let m = arr.length;
    let n = 4;
    document.write(count(arr, m, n));
</script>

Producción: 

4

Gracias a Rohan Laishram por sugerir esta versión con espacio optimizado.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Referencias: 
http://www.algorithmist.com/index.php/Coin_Change

El siguiente es otro enfoque de DP de arriba hacia abajo que utiliza la memorización:

C++

#include <bits/stdc++.h>
using namespace std;
 
int coinchange(vector<int>& a, int v, int n,
               vector<vector<int> >& dp)
{
    if (v == 0)
        return dp[n][v] = 1;
    if (n == 0)
        return 0;
    if (dp[n][v] != -1)
        return dp[n][v];
    if (a[n - 1] <= v) {
        // Either Pick this coin or not
        return dp[n][v] = coinchange(a, v - a[n - 1], n, dp)
                          + coinchange(a, v, n - 1, dp);
    }
    else // We have no option but to leave this coin
        return dp[n][v] = coinchange(a, v, n - 1, dp);
}
int32_t main()
{
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        int n, v;
        n = 3, v = 4;
        vector<int> a = { 1, 2, 3 };
        vector<vector<int> > dp(n + 1,
                                vector<int>(v + 1, -1));
        int res = coinchange(a, v, n, dp);
        cout << res << endl;
    }
}
// This Code is Contributed by
// Harshit Agrawal NITT

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    static int coinchange(int[] a, int v, int n, int[][] dp)
    {
        if (v == 0)
            return dp[n][v] = 1;
        if (n == 0)
            return 0;
        if (dp[n][v] != -1)
            return dp[n][v];
        if (a[n - 1] <= v)
        {
           
            // Either Pick this coin or not
            return dp[n][v]
                = coinchange(a, v - a[n - 1], n, dp)
                  + coinchange(a, v, n - 1, dp);
        }
        else // We have no option but to leave this coin
            return dp[n][v] = coinchange(a, v, n - 1, dp);
    }
 
  // Driver code
    public static void main(String[] args)
    {
        int tc = 1;
        while (tc != 0) {
            int n, v;
            n = 3;
            v = 4;
            int[] a = { 1, 2, 3 };
            int[][] dp = new int[n + 1][v + 1];
            for (int[] row : dp)
                Arrays.fill(row, -1);
            int res = coinchange(a, v, n, dp);
            System.out.println(res);
            tc--;
        }
    }
}
 
// This code is contributed by rajsanghavi9.

Python3

# Python program for the above approach
def coinchange(a, v, n, dp):
    if (v == 0):
        dp[n][v] = 1;
        return dp[n][v];
    if (n == 0):
        return 0;
    if (dp[n][v] != -1):
        return dp[n][v];
    if (a[n - 1] <= v):
 
        # Either Pick this coin or not
        dp[n][v] = coinchange(a, v - a[n - 1], n, dp) + coinchange(a, v, n - 1, dp);
        return dp[n][v];
    else: # We have no option but to leave this coin
        dp[n][v] = coinchange(a, v, n - 1, dp);
        return dp[n][v];
 
# Driver code
if __name__ == '__main__':
    tc = 1;
    while (tc != 0):
        n = 3;
        v = 4;
        a = [ 1, 2, 3 ];
        dp = [[-1 for i in range(v+1)] for j in range(n+1)]
        res = coinchange(a, v, n, dp);
        print(res);
        tc -= 1;
     
# This code is contributed by Rajput-Ji

C#

// C# program for the above approach
using System;
public class GFG {
 
    static int coinchange(int[] a, int v, int n, int[, ] dp)
    {
        if (v == 0)
            return dp[n, v] = 1;
        if (n == 0)
            return 0;
        if (dp[n, v] != -1)
            return dp[n, v];
        if (a[n - 1] <= v) {
 
            // Either Pick this coin or not
            return dp[n, v]
                = coinchange(a, v - a[n - 1], n, dp)
                  + coinchange(a, v, n - 1, dp);
        }
        else // We have no option but to leave this coin
            return dp[n, v] = coinchange(a, v, n - 1, dp);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int tc = 1;
        while (tc != 0) {
            int n, v;
            n = 3;
            v = 4;
            int[] a = { 1, 2, 3 };
            int[, ] dp = new int[n + 1, v + 1];
            for (int j = 0; j < n + 1; j++) {
                for (int l = 0; l < v + 1; l++)
                    dp[j, l] = -1;
            }
            int res = coinchange(a, v, n, dp);
            Console.WriteLine(res);
            tc--;
        }
    }
}
 
// This code is contributed by umadevi9616

Javascript

<script>
// javascript program for the above approach
 
    function coinchange(a , v , n,  dp) {
        if (v == 0)
            return dp[n][v] = 1;
        if (n == 0)
            return 0;
        if (dp[n][v] != -1)
            return dp[n][v];
        if (a[n - 1] <= v) {
 
            // Either Pick this coin or not
            return dp[n][v] = coinchange(a, v - a[n - 1], n, dp) + coinchange(a, v, n - 1, dp);
        } else // We have no option but to leave this coin
            return dp[n][v] = coinchange(a, v, n - 1, dp);
    }
 
    // Driver code
     
        var tc = 1;
        while (tc != 0) {
            var n, v;
            n = 3;
            v = 4;
            var a = [ 1, 2, 3 ];
            var dp = Array(n+1).fill().map(() => Array(v+1).fill(-1));
             
            var res = coinchange(a, v, n, dp);
            document.write(res);
            tc--;
        }
 
// This code contributed by umadevi9616
</script>
Producción

4

Complejidad temporal: O(M*N)
Espacio auxiliar: O(M*N)

Contribuido por: Mayukh Sinha 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *