[Algorithm] 조합수 (메모이제이션) (javaScript)

문제

재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.

입력설명

첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.

출력설명

첫째 줄에 조합수를 출력합니다.

입출력예제

입력1
5 3

출력1
10

입력2
33 19

출력2
818809200

문제 해결

const solution = (N, R) => {
  let answer;
  const memo = new Array(N + 1).fill(0).map(() => new Array(N + 1).fill(0));

  const dfs = (n, r) => {
    if (memo[n][r] > 0) return memo[n][r];

    if (r === 0 || n === r) return 1;
    else return (memo[n][r] = dfs(n - 1, r - 1) + dfs(n - 1, r));
  };

  answer = dfs(N, R);
  return answer;
};

console.log(solution(5, 3)); // 10
console.log(solution(33, 19)); // 818809200