DP-Coin Change Algorithm

//amount원 만큼을 coins[]에 있는 coin들을 사용하여 만들 수 있는 조합의 수를 구하는 method
public static long change(int amount, int[] coins) {
      
     //조합의 수를 저장할 array 생성
     long[] combinations = new long[amount + 1]; //0부터 amount까지의 숫자가 모두 들어가야 해서 size는 amount+1이 됨

     //0번째는 무조건 1
     combinations[0] = 1;

     //coins[]에 담긴 coin 하나씩 사용하여 만드는 조합의 수 카운팅하기
     for(int coin : coins) {
         for(int i = 1; i < combinations.length; i++) {
             //i가 coin보다 커질 때, 새로운 조합이 나타나게 됨
             if(i >= coin) {
                 //그러므로 i에는 새로운 조합 추가!
                 combinations[i] += combinations[i - coin];
             }
         }
     }
     return combinations[amount];
}