【第三轮】8.3-8.9 CareerCup 9.1

9.1 A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child
can run up the stairs.


回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】第归和DFS都尝试了
【时间复杂度】O(3^N)
【空间复杂度】O(N)
【gist link】
https://gist.github.com/Noahsark/75ad2e2a78efec49c33d

【解题思路】
f(n) = f(n-1) + f(n-2) + f(n-3)
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/4179ca0b0f3516c8c174

【解题思路】
DP: # of ways to reach step n equals the sum of the # of ways to reach step n - 1, n - 2 and n - 3.

【时间复杂度】
O(n)

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/happyWinner/26431c5753c080da2c82

【解题思路】
You have to use memorization for even small input like 50.
Without that the running time s exponential.

【时间复杂度】
O(N)

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/2989c58a3dced863cbb0

【解题思路】DP: # of ways to reach step n equals the sum of the # of ways to reach step n - 1, n - 2 and n - 3.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist linkhttps://gist.github.com/hilda8519/64d908e42fae1ac7a8e1

【解题思路】f(n) = f(n-1) + f(n-2) + f(n-3),use a map to reduce the runtime
【时间复杂度】
O(3^N) ?
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/bitcpf/4e7da731142acd4ddd8d

用map的时候的时间复杂度是怎么计算的，我怎么觉得不是O(N)