[LeetCode_JS] 70. Climbing Stairs _DP 기본✨

DP에 대해 아예 모르는 상태에서 문제를 풀려고 하니 기본문제라고 하는데도 풀 수 없었다.

그래서 DP에 대해 공부하고 문제를 다시 풀었고, 공부한 내용을 정리했다.

찾아보면서 좋았던 유튜브 영상 밑에 참고에 작성해놓았다.

문제

Leetcode Climbing Stairs 문제

input: 총 계단의 개수 n

output: 1칸, 2칸으로만 올라갈 수 있고, 끝까지 올라갔을 때 경우의 수

 

📌 Dynamic Programming

✱Top-down

 - 작은 문제는 해결했다는 전제하에 큰 문제부터 : f(n), f(n-1), ..., f(2), f(1)

 - 생각의 과정은 자연스럽지만 스택의 limit이 있기 때문 좋은 방식은 아니다.

 - 재귀

 

 1. 완전 재귀 → O(2^n)

2. 메모 재귀 → O(n)

재귀의 큰 문제는 너무 큰 수를 넣었을 때 RecursionError 콜스택 오버플로우 발생한다는 것!

 

✱Bottom-up

 - 가장 작은 subProblem부터 마지막 problem까지 : f(1), f(2), ..., f(n-1), f(n)

 - 배열과 for문 → O(n)

코드

var climbStairs = function (n) {
  let arr = Array(n);
  arr[0] = 1;
  arr[1] = 2;

  for (let i = 2; i < arr.length; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n - 1];
};

 

---

참고📚

유튜브 - [IOI KOREA] DP1.다이나믹 프로그래밍이란

유튜브 - [코드없는 프로그래밍] 코딩테스트, 기초, 다이나믹 프로그래밍