[Dynamic Programming] Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

 

1칸 또는 2칸씩만 계단을 오를 수 있는 경우에 대해, 총 계단수가 주어졌을때 올라갈 수 있는 가짓수는 몇개인가?

 

딱 봐도 점화식 문제다.

경우의수[n] = 경우의수[n-1] + 경우의수[n-2](n>2)가 된다.

1칸 또는 2칸만 오를 수 있댔으니, 점화식의 관점에서는 1칸전 경우의수 + 2칸전 경우의수가 현재 계단을 오를 수 있는 경우의 수가 된다는 뜻.

 

 

간단한 문제였다