算法设计：找零钱问题介绍和详细解决方案|DP-7

2021年4月14日14:48:58 发表评论 557 次浏览

本文概述

1)最佳子结构

1)不包含第m个硬币(或Sm)的解决方案。

2)包含至少1 Sm的溶液。

2)重叠子问题

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 && n>= 1)
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.io.*;

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 && n>= 1 )
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
public static void main(String[] args)
{
int arr[] = { 1 , 2 , 3 };
int m = arr.length;
System.out.println( count(arr, m, 4 ));

}

}

//This article is contributed by vt_m.``````

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 and n> = 1 ):
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 && n>= 1)
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 && \$n>= 1)
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
?>``````

``4``

``````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)
/\
/\
.      .``````

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 enteries 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 enteries 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 enteries 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
?>``````

``4``

C/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
?>``````

``4``

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