递归与贪心与动态规划

递归

递归三部曲

• 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

• 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

• 确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

一些小记

• 如果需要遍历整棵树，递归函数就不能有返回值；
• 如果需要遍历某一条固定路线，递归函数就一定要有返回值；
• 对于递归函数，如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整；
• 例如二叉树，需要返回节点时就需要用某个临时变量接住返回值，用于后序逻辑处理；
• 二叉树递归时，想着对它的左右子节点同样递归操作；
• 对于二叉树，可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度；
• 自底向上是单层递归，时间复杂度为O(n) ；而自顶向下是双层递归，时间复杂度是O(n^2)；

贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优；

动态规划:

动态规划中每一个状态是由上一个状态推导出来的，贪心则没有状态推导，而是从局部直接选最优的。

动规五步曲：

1. 确定dp数组（dp table）以及下标的含义；
2. 确定递推公式；
3. dp数组如何初始化；
4. 确定遍历顺序；
5. 举例推导dp数组；

• 做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
• 然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
• 如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
• 如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

---

【参考资料】代码随想录、力扣