LeetCode 322. Coin Change(동적 계획 및 소급법)

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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 .
Example 1:

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

Example 2:

Input: coins = [2], amount = 3
Output: -1

--------------------------------------------------------------------------------------
먼저 거슬러 올라가는 코드를 직접 썼는데 시간이 초과된 것을 발견했다.
LetCode 토론 구역에서 합리적인 욕심과 가지치기를 결합한 소급 해법을 발견했다.
Runtime: 1 ms, faster than 100.00% of Java online submissions for Coin Change.
코드는 아래와 같이 두 개의 가지치기 세부 사항을 아직 이해하지 못했다

class Solution {
        
    //1 ms
    int minCount = Integer.MAX_VALUE;//                
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        dfs(amount, coins.length-1, coins, 0);
        return minCount == Integer.MAX_VALUE?-1:minCount;
    }
    private void dfs(int amount, int start, int[] coins, int count){
        if(start<0 || count+2>minCount) return;
        
        for (int i = amount/coins[start];i>=0;i--){
            //  ：          dfs,              。     ，       
            int newAmount = amount - i*coins[start];
            int newCount = count + i;
            if(newAmount>0 && newCount+1

----------------------------------------------------------------------------------------------
다음은 동적 계획 방법입니다.
참고 주석은 이해하기 쉬울 것이다

public class Solution {
    
    public int coinChange(int[] coins, int amount) {

        int[] dp = new int[amount+1];//dp[i]     i     . i = 0,1,2,....amount
        //dp[0] = 0; //   0        0
        
        int target = 1;//     
        while(target<=amount) {
            //        0,1,2,3,...target-1      ，           target      
            int min = -1;//     target        
            for(int coin : coins) {
                if(target >= coin && dp[target-coin]!=-1) {
                    if(min==-1) min = dp[target-coin]+1; 
                    else if(dp[target-coin]+1 < min) min = dp[target-coin]+1;
                }
                //  min  -1
            }
            dp[target] = min;//   ：   sum      
            target++;
        }
        return dp[amount];
    }
    
}