labulaodong笔记

数据结构的存储方式只有两种：链式/数组。

数组存储数据结构：不需要存储额外信息，比较节省空间，可以随机访问，但是不可以动态的扩容，如果要扩容必须申请更大的内存空间然后搬运旧的元素，删除增加元素O(N)复杂度。

链表存储数据结构：需要存储额外的指针信息，需要额外的空间，不需要额外的扩容，存储空间可以看作等于内存空间，知道前驱后继的情况下增删O(1)，不可以随机的访问。

数据结构有很多，但是所有的数据结构设计出来只有一个目的：尽量高效的完成增删改查。

任何数据结构的遍历访问都可以看做两类：线性的遍历（for循环）非线性的遍历（递归）。

链表的递归遍历->二叉树的递归遍历->多叉树的递归遍历->图的递归遍历+visited数组判断是否遍历过。

很多算法都是树的问题，凡是涉及到递归的问题，都是树的问题，因为有递归树的出现。

其实很多动态规划题目，都是转化成树。暴⼒解法就是遍历⼀棵N叉树，有的时候会有重复计算的问题。

找出状态转移的方程。