거스름돈 javascript

function solution(n, money) {
    const arr = Array.from({length: n + 1}, () => 0);
    arr[0] = 1;
    
    money.forEach((e,i) => {
        for (let j = e; j < n+1; j++) {
            arr[j] += arr[j - e];
        }
    })
    return arr[arr.length - 1] % 1000000007
}

동적계획법을 활용하여 풀 수 있는 문제
규칙을 찾아 이전의 결과를 캐싱하여 경우의 수를 추가 하는 방식으로 문제를 해결할 수 있다.

처음 배열 상태
const arr = [1,0,0,...0];

1. 배열의 각 인덱스를 거스름돈으로 가정한다.
2. 각 인덱스의 값을 거스름돈으로 가능한 경우의 수로 가정한다.
3. 0원의 경우 가능한 경우의 수를 1로 가정한다.

money.forEach((e,i) => {
        for (let j = e; j < n+1; j++) {
            arr[j] += arr[j - e];
        }
    })

귀납적으로 접근하여 규칙을 찾아보면 위와 같은 규칙을 찾아낼 수 있다.