[DP] 계단 오르기

🚩 계단 오르기

 

📖 문제 설명 : 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다.

4계단을 오른다면 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 총 5가지이다.

N 계단일 때 올라갈 수 있는 방법의 수는??

 

💡 피보나치 수열을 활용한다.

 

// 계단오르기 DP

function solution(n) {
  let answer = 0
  let dp = Array.from(Array(n + 1)).fill(0)
  dp[1] = 1 // 첫 번째 계단 경우의 수
  dp[2] = 2 // 두 번째 계단 경우의 수

  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  answer = dp[n]
  return answer
}

console.log(solution(7))

👨‍💻 코드 설명

세 번째 계단으로 가는 경우는 첫 번째 계단의 경우의 수 + 2 계단 오르는 경우,

두 번째 계단의 경우의 수 + 1 계단 오르는 경우로 i-2, i-1 계단의 경우의 수와 동일하다.

즉 3가지 경우이다.

 

네 번째 계단의 경우는 두 번째 계단에서 +2 계단 오르는 경우, 세 번째 계단에서

+1 계단 오르는 경우이다. 즉 2+3 = 5가지이다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.