70. Climbing Stairs

70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

문제

풀이

n = 2일 때 (1,1) (2)
n = 3일 때 (1,1,1) (1,2) (2,1)
n = 4일 때 (1,1,2) (2,2) (1,1,1,1) (1,2,1) (2,1,1) 이다.
여기서 점화식을 구할 수가 있는데 dp[i] = dp[i-1] + dp[i-2]이다. 그 이유는
dp[i-1]인 것은 한 계단전 경우의 수인데 거기서 한 계단 올라가면 dp[i]를 구할 수 있고
dp[i-2]는 두 계단전 경우의 수인데 거기서 두 계단 올라가면 dp[i]를 구할 수 있다.

결과