Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Solution: Minimum Coin Change

Introduction

Given an infinite supply of ‘n’ coin denominations and a total money amount, we are asked to find the minimum number of coins needed to make up that amount.

Example 1:

Denominations: {1,2,3}
Total amount: 5
Output: 2
Explanation: We need a minimum of two coins {2,3} to make a total of '5'

Example 2:

Denominations: {1,2,3}
Total amount: 11
Output: 4
Explanation: We need a minimum of four coins {2,3,3,3} to make a total of '11'

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Avinash Agarwal

· 4 years ago

class Solution { public int coinChange(int[] coins, int amount) { if(amount == 0) return 0; if(coins.length == 0 && amount > 0) return -1;

int[] dp = new int[amount+1];

Arrays.fill(dp, amount+1); dp[0] = 0;

for(int i=1; i