字典树，即 Trie 树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引 擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
1.结点本身不存完整单词；
2.从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串；
3.每个结点的所有子结点路径代表的字符都不相同。
Trie 树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
通过函数体来进行的循环
通过参数进行传递变量 Python递归模板：
def recursion(level, param1, param2, ...):
#recursion terminator
if level > MAX_LEVEL:
process_result
return
#process logic current level
process(level, data...)
#drill down
self.recursion(level + 1, p1, ...)
#reverse the current level status if needed
不同路径2状态转移方程
//i,j > 0
dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
| 运算符 | 含义 |
|---|---|
| << | 左移 |
| >> | 右移 |
| >>> | 无符号右移 |
| & | 按位与 |
| | | 按位或 |
| ~ | 按位取反 |
| ^ | 按位异或 |
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
共性：找到重复子问题
差异性：最优子结构、中途可以淘汰次优解
1.最优子结构
2.定义状态空间
3.DP方程
visited = set()
def dfs(node, visited):
# terminator
if node in visited:
return
visited.add(node)
# process current node here.
...
for next_node in node.children():
if next_node not in visited:
dfs(next_node, visited)
在内存中开辟出的一块连续空间
| 操作 | 复杂度 |
|---|---|
| 查找 | O(1) |
| 插入 | O(n) |
| 删除 | O(n) |
| prepend | O(1) |
| append | O(1) |