[LeetCode] 518. Coin Change II

😎풀이

1. DP를 사용하여 현재 금액을 만들 수 있는 경우의 수 계산
2. 0원은 아무 코인도 채우지 않는 경우의 수로 만들 수 있으므로 1 정의
3. coin을 1씩 증가시키며 총액까지 만들 수 있는 금액 누산
   3-1. 이전 금액에서 coin을 통해 만들 수 있는 경우의 수만큼 누적
4. amount를 만들 수 있는 경우의 수 반환

function change(amount: number, coins: number[]): number {
    const n = coins.length
    const dp = Array(amount + 1).fill(0)
    dp[0] = 1
    for(const coin of coins) {
        for(let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin]
        }
    }
    return dp[amount]
};