You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
import java.util.Arrays;
class Solution {
static final int MAX_INF = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
for (int[] arr : dp) {
Arrays.fill(arr, -1);
}
int res = minCoinsReq(coins, amount, n,new ArrayList<Integer>(), dp);
if (res == MAX_INF -1) {
return -1;
}
return res;
}
public int minCoinsReq(int[] coins, int amount, int n, ArrayList<Integer> curCoinsList, int[][] dp){
if(amount ==0){
return curCoinsList.size();
}
if(n==0){
return MAX_INF-1;
}
if(dp[n][amount]!=-1 ){
return dp[n][amount];
}
if(coins[n-1]<=amount){
int coinAtIdxNotIncluded = minCoinsReq(coins,amount,n-1,curCoinsList,dp);
curCoinsList.add(coins[n-1];)
int coinAtIdxIncluded = minCoinsReq(coins,amount-coins[n-1],n, curCoinsList,dp);
curCoinsList.remove(curCoinsList.size()-1);
return dp[n][amount]= Math.min(coinAtIdxIncluded,coinAtIdxNotIncluded);
}else {
return dp[n][amount]= minCoinsReq(coins,amount,n-1, curCoinsList,dp);
}
}
}
- The base cases are incorrect.
- Also, the
dphas not been properly populated. - The recursive calls for updating the current coins list are not properly handled.
Code
import java.util.Arrays;
class Solution {
static final int MAX_INF = Integer.MAX_VALUE;
public static void main(String[] args) {
Solution solution = new Solution();
int[] coins = { 1, 2, 5 };
int amount = 11;
int result = solution.coinChange(coins, amount);
System.out.println(result);
}
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
for (int[] arr : dp) {
Arrays.fill(arr, -1);
}
int res = minCoinsReq(coins, amount, n, dp);
if (res == MAX_INF - 1) {
return -1;
}
return res;
}
public int minCoinsReq(int[] coins, int amount, int n, int[][] dp) {
if (amount == 0) {
return 0;
}
if (n == 0) {
return MAX_INF - 1;
}
if (dp[n][amount] != -1) {
return dp[n][amount];
}
if (coins[n - 1] <= amount) {
int coinAtIdxNotIncluded = minCoinsReq(coins, amount, n - 1, dp);
int coinAtIdxIncluded = minCoinsReq(coins, amount - coins[n - 1], n, dp);
if (coinAtIdxIncluded != MAX_INF - 1) {
coinAtIdxIncluded++;
}
return dp[n][amount] = Math.min(coinAtIdxIncluded, coinAtIdxNotIncluded);
} else {
return dp[n][amount] = minCoinsReq(coins, amount, n - 1, dp);
}
}
}