memory 用list来记和用哈希表来记的区别是什么？
来源：9-2 第一个动态规划问题 Climbing Stairs
皓哥卷起来
2021-03-15
老师好，我在做DP 这块的练习的时候有个疑问。记忆化搜索的方法需要memory，因为课上出现的需要存的内容基本都是 {index：子问题在index 下的解} 这样形式，而index 很容易排列在list里，所以放进list 中来记录memory。
但这样往往需要把memory 先初始化成-1，然后在记录的时候替换成非负的数值。这样做的话一方面会依赖于解的非负性，对于可能出现负数解的情况还会有点麻烦，另一方面也是因为index 很容易排列在list里，但是要是问题变了下，需要存的是一些图的节点或者是更复杂的东西，不好直接排布在index中来记录memory。
但上面的问题很容易用哈希表解决，算了一个子问题的解之后就创立一个键值对存进去。list 里按照索引取值是O(1) 的，哈希表里查找也是O(1) 的，那为什么不全部抛弃memory 的list 的记法，去用哈希表呢？我不知道这里面是不是有什么深层的原因，希望能得到解答！谢谢！
写回答
1回答
-
因为哈希表只是理论复杂度是 O(1) 的，实际上无论是存还是取，性能消耗都比直接使用数组慢。如果你多做一些问题，每个问题都尝试既使用哈希表求解，又使用数组求解，应该可以观察到很多问题哈希表的耗时比数组大；甚至有使用哈希表超时，使用数组通过的情况，
另外，哈希表的实际消耗空间也有可能比数组大，但是如果状态稀疏，哈希表是更可行的方式。
继续加油！：）
112021-03-15
相似问题