와 이건 뭐야ㅋㅋㅋㅋㅋㅋ 하면서 한참 분석하다가
입력: 세로길이 2 가로길이 n인 보드
출력: 2 by 1 크기의 타일로 보드를 채우는 모든 경우의 수 리턴
n:1 = 1
n:2 = 2
n:3 = 3
n:4 = 5
뒤에 오는 패턴은 앞에 온 2가지의 타입의 조합이다. 세로로만 조합, 가로로만 조합, 가로 * 세로조합
가로길이 n = (n-1)세로패턴 + (n-2)가로패턴
어...? 이거 피보나치랑 비슷한데? 함
n이 1일때 1이고 n이 2일때 2라는 거만 빼면 뒷 숫자는 앞 숫자 두개의 합이라는 것을 알 수 있다!
그래서 피보나치로 해결을 해보려고 했으나 실행시간이 초과됨...ㅜ
뒤에오는 패턴은 앞에 온 2가지의 타입의 조합이니까 또 며칠간 본 메모를 쓰면 될 것 같은데 문제는 이걸 어케하는거지???

let tiling = function (n) {
  let result = 0;
  if(n < 3){ //base case
    n === 1 ? result += 1 : result += 2; 
  } else { //recursive case
    result = result + (tiling(n-1) + tiling(n-2));
  }
  return result;
};

동적계획법: 중복되는 부분 문제를 재귀를 사용해서 상향식으로 처리하는 기법
메모이제이션: 중복되는 연산 부분을 제거하기 위해 사용함

메모이제이션 memoization

로컬 캐쉬기술 중 하나. 메모리에 특정 정보를 기록해두고 필요할때마다 정보를 가져와 활용한다.
로컬 캐쉬를 사용하는 성능 개선을 하기 위해 사용한다.
재귀 + 메모이제이션을 함께 쓰도록 하자!!

1. 메모장을 만든다(매개변수로 만들어도 ok)

const fib = (n, memo) => {
  memo = memo || {}
  if (memo[n]) return memo[n]
  if (n <= 1) return 1
  return memo[n] = fib(n-1, memo) + fib(n-2, memo)}

변경되지 않고 스코프 내에서 계속해서 값을 유지할 수 있도록 클로저를 사용해야 한다.

2. 메모 객체를 매개변수로 받았는지 확인하고 그렇지 않은 경우 빈 객체로 설정

memo = memo || {}

3. 메모에 값이 있는지 확인하고 있다면 그것을 반환

if (memo[n]) return memo[n]

4. 메모에 없다면 재귀함수를 다시 호출하지만 메모를 매개변수로 전달. 반환 전 결과를 캐시에 추가한다

return memo[n] = fib(n-1, memo) + fib(n-2, memo)

memoization 참고
https://www.devh.kr/2020/Understanding-Memoization-In-JavaScript/
https://www.freecodecamp.org/news/memoization-in-javascript-and-react/

최종적으로 제출한 답!

let tiling = function (n) {
  const memo = {};

  const recur = (n) => {
    if(memo[n]) return memo[n];
    if(n < 3) return n;

    memo[n] = recur(n-1) + recur(n-2);
    return memo[n];
  }
  return recur(n);
}