Coin Change Problem

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Input: coins = [2], amount = 3
Output: -1
Input: coins = [1], amount = 0
Output: 0
Input: coins = [1], amount = 1
Output: 1
Input: coins = [1], amount = 2
Output: 2
  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104
public class Solution {
public int CoinChange(int[] coins, int amount) {
// Create an DP array where we will store the solution of subproblem from bottom-up approach.
// As it will have value for 0 also so we will have Amount+1 length;
int[] dp = new int[amount + 1];

// Initialize the DP array with sum dummy value.
for(int i = 0 ; i < dp.Length ;i++)
{
dp[i] = -99; // You can initialize with any value greater than the "amount" value.
}
dp[0] = 0;
for(int i = 1 ; i < amount+1 ; i++)
{
for(int j = 0 ; j < coins.Length ; j++)
{
if( i-coins[j] >=0)
{
dp[i] = Math.Min(dp[i], 1 + dp[i-coins[j]]);
}
}
}
return dp[amount] == -99 ? -1:dp[amount];
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store