note:

动态规划有四个特点

1. 求最优解
2. 整体问题的最优解依赖于各个子问题的最优解
3. 大问题可以分解为若干个小问题，这些小问题之间还存在重叠的更小的子问题
4. 从上往下分析问题，从下往上求解问题

——摘自《剑指offer》

note:此类型题目（路径搜索）一般深度优先搜索和广度优先搜索是最优解。方向数组也是常用的小技巧。

note:典型的迷宫找路的问题，一般都是使用基于dfs+剪枝的回溯方法。

note: 虽然本科的时候讲递归必讲斐波那契，但是不意味着递归最适合于斐波那契，因为存在很多重复计算，且递归也需要额外空间。

还有关于求余的问题，有三个公式需要记一下

$$(x+y)\%p = (x\%p+y\%p)\%p \\ (x-y)\%p = (x\%p-y\%p)\%p \\ (x*y)\%p = (x\%p*y\%p)\%p$$

note:拿到手就要意识到是二分查找。然后思考数组的特性，选定target和每次边界移动的方式。

note: 这道题乍一看非常简单，当然做起来也很简单，但是中间过程如何简化就需要再想一想。每次删除和增加操作都需要“倒空”么？高效的回答当然是否定的。

note: 知道任何两种遍历的方式，来重建二叉树是非常经典的数据结构题目。思路非常的简单，实现起来却没有思考时写写画画那么简单。其中重点我觉得是一种将子树看为全新的树的思想。

note: insert方法虽然好写但是时间复杂度一般很高，反转链表虽然不错但是需要问清楚是否可以改动原链表

Note： 可能在面试的时候需要问清楚原字符串是否可以改动，可以的话我们利用c++ string的特性原地操作，不可以的话就需要重新new一个string。总之是一个很简单的题目，可能需要注意的是string的resize方法可以扩充string的大小

Note：比遍历时间更优的除了二分，还有减治，当然二分就是一种减治的思想，但是减治不一定必须二分。