[알고리즘] [leetCode] Climbing Stairs

참고

Dynamic programing

= 큰 문제를 작은문제로 나눠서 푸는 알고리즘

엥 이거 divide conquer 아니냐?

dynamic programming 은 memoization 이 들어가는 점에서 다르다.

☢️ 조건

1> 겹치는 부분이 있어야 ( overlapping Subproblem )

• 전체 문제가 여러개의 부분 문제로 나눠지는지
  ex> 피보나치 수열의 20번째 항을 구하기

1번째항 구하기
2번째항 구하기
3번째항 구하기
...
20번째항 구하기

2> 최적 부분 구조가 있어야 ( Optimal Substructure )
ex> 피보나치 수열의 20번째 항을 구하기

3번째 = 0+1
4번째 = 2번째 +3번째
....
20번째 = 18번째 + 19번째

Memoization

부분문제를 중복으로 연산하지 않기 위함

ex> 3번째 계산했는데 또 계산하지 않도록

var climbStairs = function (n) {
  let memo = Array(n + 1);

  // n=1 0
  // n=2 1
  // n=3 3
  memo[1] = 1;
  memo[2] = 2;
  function fibo(n) {
    if (n < 3) {
      // 이미 계산한 값을 중복해서 계산하지 않음 
      return memo[n];
    } else {
      // 이미 계산한 값을 중복해서 계산하지 않음 
      if (!!memo[n]) {
        return memo[n];
      }
// 작은 문제를 해결한 것을 누적해서 큰 문제를 해결함 
      // n 번째 값을 구하기 위해 n-2 n-1 로 나눠서 값을 구하고
      // 합침 
      memo[n] = fibo(n - 2) + fibo(n - 1);

      return memo[n];
    }
  }

  return fibo(n);
};