https://www.hackerrank.com/challenges/ctci-recursive-staircase/problem N개의 계단이 주어졌을 때 1, 2, 3번의 걸음으로 가는 모든 경우의 수를 구하는 문제다. 처음에는 DFS를 이용하는 줄만 알고 재귀호출을 이용한 DFS를 구현해서 풀었으나 타임아웃이 나와 2시간이나 헤메었다. 도저히 생각이 안나 해당 문제의 Discussions 게시판을 참고했고, 알고보니 이 문제는 아래의 피보나치 수 구하는 문제와 매우 비슷한 문제였다. 나는 피보나치 수열이 점화식으로 표현이 된다는 점은 알고 있었지만 점화식에 대한 응용법과 정확한 개념을 알지 못했었다. 그래서 이 문제를 풀면서 이 문제가 점화식을 활용한 DP 풀이로 해결할 수 있을 거라고 생각하지 못했다..