코인체인지 리트코드

서로 다른 액면가의 동전을 나타내는 정수 배열 동전과 총 금액을 나타내는 정수 금액이 제공됩니다.

해당 금액을 구성하는 데 필요한 가장 적은 수의 동전을 반환하십시오. 동전의 조합으로 그 금액을 만들 수 없는 경우 -1을 반환합니다.

각 종류의 동전이 무한한 수라고 가정할 수 있습니다.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount ==0) return 0;
        // we will use dynamic prgramming for  solving this 
        // bottom-up approach
        int dp[][] = new int[coins.length][amount+1];
        for(int row[]: dp) Arrays.fill(row,-1);
        // we will start from last index and go to first index
        int coinsNeeded = findSmallestList(coins.length-1,coins,amount,dp);
        return coinsNeeded ==(int)1e9 ? -1 : coinsNeeded;
    }
    public int findSmallestList(int index,int[] coin,int amount,int dp[][]){
       if(index==0){
           if(amount % coin[index] ==0){
               return amount/coin[index];
           }
           return (int)1e9;
       }
      if(dp[index][amount]!=-1) return dp[index][amount];

        int left =(int)1e9;
        //take same index value
        if(amount>=coin[index]){
            left = 1+ findSmallestList(index,coin,amount-coin[index],dp);
        }
        //take next index 
        int right = 0+ findSmallestList(index-1,coin,amount,dp);
        //System.out.println(Integer.min(left,right));
        return dp[index][amount] =Integer.min(left,right); 
    }
}

하향식 접근 방식, 즉 Dp의 Tabulation 접근 방식을 사용하여 스택 공간을 제거할 수 있습니다.