dim4o

SumWithUnlimitedAmountOfCoins

Oct 21st, 2015
101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public static class SumWithUnlimitedAmountOfCoins
  2.     {
  3.         public static void Main()
  4.         {
  5.             Console.Write("S = ");
  6.             int targetSum = int.Parse(Console.ReadLine());
  7.             Console.Write("Coins = ");
  8.             string input = Console.ReadLine();
  9.             int[] coins = input.Split(new char[] { '{', '}', ',' }, StringSplitOptions.RemoveEmptyEntries)
  10.                 .Select(c => int.Parse(c)).ToArray();
  11.  
  12.             Console.WriteLine(GetCount(targetSum, coins));
  13.         }
  14.  
  15.         public static int GetCount(int targetSum, int[] coins)
  16.         {
  17.             int[,] memo = new int[coins.Length, targetSum + 1];
  18.  
  19.             // Fill the memo matrix
  20.             for (int row = 1; row < memo.GetLength(0); row++)
  21.             {
  22.                 memo[row, 0] = 1;
  23.                 for (int col = 1; col < memo.GetLength(1); col++)
  24.                 {
  25.                     if (coins[0] <= col && col % coins[0] == 0)
  26.                     {
  27.                         memo[0, col] = 1;
  28.                     }
  29.                     if (coins[row] > col)
  30.                     {
  31.                         memo[row, col] = memo[row - 1, col];
  32.                     }
  33.                     else
  34.                     {
  35.                         memo[row, col] = memo[row - 1, col] + memo[row, col - coins[row]];
  36.                     }
  37.                 }
  38.             }
  39.  
  40.             return memo[coins.Length - 1, targetSum];
  41.         }
  42.     }
RAW Paste Data