조합의 경우수(메모이제이션)

코드

  function solution(n, r) {
    let answer = [];
    let dy = Array.from(Array(34), () => Array(34).fill(0));

    function DFS(n, r) {
      if (dy[n][r] > 0) return dy[n][r];

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

    answer = DFS(n, r);

    return answer;
  }

해결 방법

이 풀이는 n = 5, r = 3로 가정한 풀이이다.

조합은 n === r 이거나 r이 1이면 값이 1이라 1을 반환해주면 된다.

n !== r이나 r !== 1이면 DFS(n-1, r-1) + DFS(n-1, r)을 하여 반환해줘야 한다. 하지만 n의 값이 커지면 시간이 오래 걸려서 메모이제이션을 해야한다. 그렇기에 dy에 값을 저장해둔다. 만약 DFS(n, r)을 이미 구했던 것이면 dy[n][r]의 값이 0보다 커서 그 값을 그대로 가져와 주면 속도를 개선시켜준다.