memoization

function fibonacci(n) {
  const memo = [0, 1];

  function fib(n){ //서브함수를 만든다.
    if(memo[n] !== undefined) return memo[n]; 
    //서브펑션 내에서 메모에 해당 값이 있는지 확인한다. 
    //여기서 if(memo[n]) 으로 하면 기존에 메모에 o,1을 할당해주었기 때문에 true가 된다. 
    //무조건 memo[n]을 리턴하게됨;;;; 그럼 무한반복;;;
    memo[n] = fib(n-1) + fib(n-2); //서브펑션에 쪼갠 식을 계산한 값을 메모한다
    return memo[n]; //memo[n]값을 넘겨줌
  }
  return fib(n); //서브함수 실행
}

내가 한 실수..헿

1. memo에 처음엔 빈 배열을 주었다. 이건 상황에 따라 다르겠지만 피보나치는 일단 변수가 0,1을 갖고 있어야 한다!
   이걸 깨닫고 0,1을 줌 오키 해결
2. if문을 recursive 함수 바깥에 두었다.
   n에 0이나 1이 들어오면 바로 리턴하려고 그랬던 건데... 실수였음
   if문을 recur함수 안에 두지 않으면 이 함수가 실행될 때 memo에 값이 있는지 없는지 상관없이 다 계산을 하것지 의미없는 짓이도다ㅋㅋㅋㅋ
3. recur함수 내에서 부모함수를 자꾸 부르는 실수를 저지름...!!@.@
4. recur함수를 실행시켜야 하는데 그걸 빼먹음. 안쓸거면 왜만들었냐

담에 fib가 아닌 경우에 메모이제이션을 하는 것을 분석해봐야겠다!!
그럼 확실히 이해될듯!!

https://youtu.be/2RwlzBDhGh4
서울대 나오신 어떤분께서 다이나믹 프로그래밍에 대해 설명하신 유튜브 영상이다. 느므느므 설명 잘해주심! 아마 c언어로 예시를 드신 것 같다!
그래서 예시를 보고 자바스크립트 코드로 옮겨봄

let memo = [0,1];
function recur(n){
    if(n <= 1) return memo[n];
    if(memo[n] !== undefined) return memo[n];
    memo[n] = recur(n-1) + recur(n-2);
    return memo[n];
}

이렇게 따로 서브함수를 만들지 않고 계산할 수도 있다. 이때는 memo를 전역변수에 두었음. 재귀되는 함수와 별개로 선언을 해야하는건가! 여튼 위에 쓴 예시보다 간결하고 더 읽기 좋은 것 같다.

밑에서부터 계산: 반복문

function fib(n){
  let result = [0, 1];
  if(n < 2) return n;
  for(let i = 2; i <= n; i++){
    result[i] = result[i-1] + result[i-2];
  }
  return result[n];
}