[알고리즘] 2 x 1 타일로 보드를 채우는 경우의 수

세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.

let tiling = function (n) {
  // 2 x n 보드를 2 x 1 타일로 채우려면
  // n = 1일 때 1가지, n = 2일 때 2가지(가로, 세로)
  // n = 3일 때 3가지, n = 4일 때 5가지
  const memo = [0, 1, 2];
  // 경우의 수를 저장하는 변수
  const aux = (size) => {
    if (memo[size] !== undefined) return memo[size];
    // 이미 경우의 수가 저장되어 있는 값이면 바로 꺼내서 리턴
    if (size <= 2) return memo[n];
    // 2보다 작을 때도 이미 저장해주었으므로 바로 꺼내서 리턴
    memo[size] = aux(size - 1) + aux(size - 2);
    // 경우의 수가 저장되어 있지 않으면 피보나치 수열로 더해서 리턴
    return memo[size];
  };
  return aux(n);
};