fork download
copy 
  1. using System;
  2.  
  3. public class Test
  4. {
  5. 	public static void Main()
  6. 	{
  7. 		//http://w...content-available-to-author-only...s.org/dynamic-programming-set-7-coin-change/#comment-2739406149
  8. 		//http://a...content-available-to-author-only...n.com/dynamic-programming-coin-change-problem/
  9. 		//http://w...content-available-to-author-only...t.com/index.php/Coin_Change
  10. 		var coins = new int[]{3,2,1};
  11. 		var changeRequiredForAmount = 5;
  12. 		Console.WriteLine("Find Different Ways to provide change:");
  13. 		Console.WriteLine("Amount: {0} using unlimited supply of denominations of [{1}]",changeRequiredForAmount, string.Join(" , ",coins));
  14.  
  15. 		Console.WriteLine();
  16. 		Console.WriteLine("Total number of ways (Recursion): {0}",FindDifferentWaysToProvideChange(coins,coins.Length,changeRequiredForAmount));
  17.  
  18. 		Console.WriteLine();
  19. 		Console.WriteLine("TOtal number of ways using DP: {0}",FindDifferentWaysToProvideChangeDP(coins,changeRequiredForAmount));
  20. 	}
  21.  
  22. 	private static int FindDifferentWaysToProvideChange(int[] coins,int totalDenomination, int changeForAmount)
  23. 	{
  24. 		//Console.WriteLine("Total Denomination: {0}, changeForAmount: {1}",totalDenomination,changeForAmount);
  25. 		if(changeForAmount == 0)
  26. 			return 1;
  27.  
  28. 		if(changeForAmount < 0)
  29. 			return 0;
  30.  
  31. 		if(totalDenomination <= 0 && changeForAmount >= 1)
  32. 			return 0;
  33.  
  34. 		return FindDifferentWaysToProvideChange(coins, totalDenomination-1,changeForAmount) +
  35. 			FindDifferentWaysToProvideChange(coins, totalDenomination,changeForAmount-coins[totalDenomination-1]);
  36. 	}
  37.  
  38. 	private static int FindDifferentWaysToProvideChangeDP(int[] coins,int changeForAmount)
  39. 	{
  40. 		var totalDenominationTypes = coins.Length;
  41. 		var amount = changeForAmount;
  42. 		var solutionMatrix = new int[totalDenominationTypes+1,amount+1];
  43.  
  44. 		for(int i=0;i<=totalDenominationTypes;i++)
  45. 			solutionMatrix[i,0] = 1;
  46.  
  47. 		for(int j=0;j<=amount;j++)
  48. 			solutionMatrix[0,j] = 0;
  49.  
  50. 		for(int i=1;i<=totalDenominationTypes;i++)
  51. 		{
  52. 			for(int j=1;j<=amount;j++)
  53. 			{
  54. 				if(coins[i-1] <= j)
  55. 				{
  56. 					solutionMatrix[i,j] = solutionMatrix[i - 1,j] + solutionMatrix[i,j - coins[i - 1]];
  57. 				}
  58. 				else
  59. 					solutionMatrix[i,j] = solutionMatrix[i - 1,j];
  60. 			}
  61. 		}
  62. 		Console.WriteLine("********************* DP SolutionMatrix: ********************");
  63. 		for(int i=0;i<=totalDenominationTypes;i++)
  64. 		{
  65. 			for(int j=0;j<=amount;j++)
  66. 			{
  67. 				Console.Write(" {0} ",solutionMatrix[i,j]);
  68. 			}
  69. 			Console.WriteLine();
  70. 		}
  71. 		Console.WriteLine();
  72.  
  73. 		return solutionMatrix[totalDenominationTypes,amount];
  74. 	}
  75. }
Success #stdin #stdout 0.04s 23976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Find Different Ways to provide change:
Amount: 5 using unlimited supply of denominations of [3 , 2 , 1]

Total number of ways (Recursion): 5

********************* DP SolutionMatrix: ********************
 0  0  0  0  0  0 
 1  0  0  1  0  0 
 1  0  1  1  1  1 
 1  1  2  3  4  5 

TOtal number of ways using DP: 5
https://ideone.com/aaTymC
[DP][Recursion] Coin Change Problem.
language:
C# (gmcs 5.20.1)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!