DP - 동전

• 목표 30원, [5원, 6원, 7원]이 주어졌을 때..
  1~4원은 5, 6, 7원으로 만들 수 없음
  5만 사용했을 때 5원 ~ 30원 까지의 경우의 수를 구함
  => 5, 6 사용했을 때 5원 ~ 30원까지의 경우의 수
  => 5, 6, 7 사용했을 때 5원 ~30원까지의 경우의 수

d[i][j]
----5 6 7 total
05 1 0 0 1
06 0 1 0 1
07 0 0 1 1
08 0 0 0 0
09 0 0 0 0
10 1 0 0 1
11 0 1 0 1 ==> dp[11-6] = dp[5] = 1
12 0 1 1 2
13 0 0 1 1
14 0 0 1 1
15 1 0 0 1
16 0 1 0 1
17 0 1 1 2
18 0 1 1 2
19 0 0 2 2
20 1 0 1 2
21 0 1 1 2
22 0 1 1 2
23 0 1 1 2
24 0 1 2 3
25 1 0 2 3
26 0 1 2 3
27 0 1 2 3
28 0 1 2 3
29 0 1 2 3
30 1 1 2 4 ==> dp[30-7] = dp[23] = 2

dp[30]의 total은 4

function coin(target, type) {
  const dp = Array(target + 1).fill(0);
  dp[0] = 1;

  for(let i = 0 ; i < type.length ; i++){
    for(let j = type[1] ; j < dp.length ; j++){
      dp[j] = dp[j] + dp[ j - type[i] ];
    }
  }

  return dp[target];
}