https://programmers.co.kr/learn/courses/30/lessons/12914
-
flow
이거 옛날에 풀었던 2xN 타일링 문제와 같은 방식으로 풀 수 있다. 보면 f(n) = f(n-1)+f(n-2) 의 점화식이 정답이 됨을 쉽게 파악할 수 있다. f(n-2) 모든 경우의 수에서 2칸 뛰는 것과 f(n-1) 모든 경우의 수에서 1칸 뛰는 것을 합하면 f(n) 경우의 수.. 정답이 피보나치 수열하고 일치하게 된다...
이런 dp는 당연히 O(N) 깔끔 -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A18.py
