求大神解释CC150 9.1爬阶梯递归问题

miss_snow 发表于 2014-10-10 22:17
额……不好意思，繁体字不太懂……囧
你问的是，为什么时间复杂度是O(N)，但没开什么空间？
时间和空间 ...

你看二楼那位递归的代码，我感觉没开数组啊，怎么空间复杂度是O（N）？时间复杂度我知道

TonyJang 发表于 2014-10-10 22:22
你看二楼那位递归的代码，我感觉没开数组啊，怎么空间复杂度是O（N）？时间复杂度我知道

因为他用了动态规划啊
这里动态规划和记忆化搜索的复杂度一样
动态规划写的话就是三个初始值，然后一遍for循环，就是O(N)了

lz你是一遍刷G一遍刷题吗？？？

miss_snow 发表于 2014-10-10 23:15
lz你是一遍刷G一遍刷题吗？？？

對啊，我轉專業的，要是找不到工作就去讀個CS的學位

TonyJang 发表于 2014-10-10 23:20
對啊，我轉專業的，要是找不到工作就去讀個CS的學位

哦哦，lz加油O(∩_∩)O哈！