本文概述

• C++
• Java
• Python3
• C#
• PHP
• C++
• C
• Java
• python
• C#
• PHP
• C/C++
• Java
• python
• C#
• PHP

给定一个值N, 如果我们要N分钱找零, 并且我们有无限数量的S = {S1, S2, .., Sm}硬币的供应, 我们可以用几种方法进行找零？硬币的顺序无关紧要。
例如, 对于N = 4和S = {1, 2, 3}, 有四个解：{1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}。因此输出应为4。对于N = 10且S = {2, 5, 3, 6}, 有五个解：{2, 2, 2, 2, 2}, {2, 2, 3, 3} {2, 2, 6}, {2, 3, 5}和{5, 5}。因此输出应为5。
1)最佳子结构
要计算解决方案的总数, 我们可以将所有解决方案分为两组。
1)不包含第m个硬币(或Sm)的解决方案。
2)包含至少1 Sm的溶液。
设count(S [], m, n)为计算解数的函数, 则可以写为count(S [], m-1, n)和count(S [], m, n-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

应该注意的是, 上述函数一次又一次地计算相同的子问题。请参见以下递归树, 其中S = {1, 2, 3}, n = 5。
函数C({1}, 3)被调用两次。如果我们绘制完整的树, 则可以看到有许多子问题被多次调用。

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

由于再次调用了相同的问题, 因此此问题具有"重叠子问题"属性。因此, 硬币更改问题具有两个属性(请参见这个和这个)的动态编程问题。像其他典型的动态编程(DP)问题, 可以通过自下而上的方式构造一个临时数组table [] []来避免相同子问题的重新计算。
动态编程解决方案
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 + yreturn 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

时间复杂度：O(百万)
以下是方法2的简化版本。此处所需的辅助空间仅为O(n)。
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

【算法设计（找零钱问题介绍和详细解决方案|DP-7）】感谢Rohan Laishram提出此空间优化版本的建议。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
参考文献：
http://www.algorithmist.com/index.php/Coin_Change

推荐阅读

• 

  开挖地下室如何做防水
• 

  现在象棋比赛有和棋黑胜,这样的赛制合理吗？
• 

  快手刷粉用的什么工具免费 揭露1个小时可以免费增加1万粉丝的方法
• 

  church 039 s如何
• 

  元神有多少个服务器？如何区分它们？ 元神有几个服务器怎么区分
• 

  如梦令【除夕看春晚】
• 

  描写家乡变化的段落要短而精巧
• 

  英语四级听力题目类型 四级听力多少分
• 

  社会实践部申请书
• 

  深蹲|每天深蹲的好处，不止一点点，其中讲究，禁忌人群要记牢
• 

  微信显示手机号码怎么取消（微信显示手机号码怎么设置）
• 

  绵阳热水器维修上门维修,了解全面才好决定
• 

  抖音如何显示位置？抖音显示位置方法攻略介绍！
• 

  王者荣耀主播十月首周人气排行,张大仙排名榜首,人气快到梦泪十倍,是否太恐怖？
• 

  墨西哥玫瑰红蟒的饲养方法 墨西哥玫瑰红蟒的饲养方法图解
• 

  怪物猎人崛起雪鬼兽怎么速刷 电锯速刷雪鬼兽攻略分享
• 

  龙井茶属于绿茶吗
• 

  Photoshop调出照片偏暗的红褐色
• 

  苹果4iphone已停用怎么刷机,苹果4怎么刷机和越狱啊？
• 

  查询个人订票信息方法 123606火车票官网订票收费吗

• 邮递员面试经验| 2020年软件工程实习（校外）
• Python探索相关性详细指南
• SQL中自然联接和内部联接之间的区别
• 高级算法（跳转指针算法原理介绍和实现）
• 转（Android-apt）
• Android使用代码设置Dialog的Style
• Android 反编译工具
• android:layout_weight属性的使用方法总结
• 张高兴的 Xamarin.Android 学习笔记（环境配置）