사실, 피보나치 문제가 아니라, 직접 경우의 수에 대한 점화식을 세워보시면,
피보나치 수열의 점화식과 같다진다고 보는게 나을 것 같습니다.

한 번 가는데, 1칸 또는 2칸을 점프할 수 있다고 하면,
현재 n칸째의 경우의 수를 구해본다고하면, n-1칸에서 1칸 뛰어서 온경우, n-2칸에서 2칸 뛰어서 온 경우
말고는 존재하지 않습니다.

이렇게 되면,
dp[n] = dp[n-1] + dp[n-2]
라는 점화식이 세워지는데,

그냥 단순히 이 점화식이, 피보나치 수열과 같다고 생각하시면 될 것 같습니다.
사실 이 문제는, 문제에 거의 점화식이 주어졌다고 생각해도 되는 문제라서,
직관적으로 바로 풀이가 떠오르는 경우가 많을겁니다.