一个方法让你秒杀所有递归题

不好意思标题党了🐶，这个帖子主要用来总结我在FLAG几年工作中学习到关于API Design中我个人认为最重要的一个原则以及在刷题过程中的应用。再次刷leetcode，这条原则给了我完全不同的感受。

tl;dr   Principle: Contract First

关于Contract First API Design,这个link可以给大家一些介绍。总结起来就是在coding之前要 1）把问题拆成明确的子模块，并 2）用明确的Contract（合约）描述各个模块API接口提供的功能。这一点和算法中的递归概念不谋而合。在递归中我们会 1）明确定义问题与可以被分解的子问题，2）假设子问题可以被解决，考虑如何把子问题合并解决原问题，3）明确递归终止/边境条件。我们可以看到递归问题的解决只是比Contract design多需要思考如何终止递归 3）这一步骤，逻辑上它们非常一致。下面我拿leetcode的两个不同难度的题举例说明一下，解释都在leetcode discussion的comment里。

LC 114. Flatten Binary Tree to Linked List (Medium)
Solution

LC 124. Binary Tree Maximum Path Sum (Hard)
Solution

在这个过程中，有两点应该值得参考。
  （1）在考虑子问合并解决原问题时不要去考虑递归终止条件。把注意力集中在“假设我能够通过call这个递归函数解决子问题，我怎么能通过子问题解决原问题”。例如LC114中，要关注的问题是假设我已经能把左子树或者右子树flatten，我如何把flatten好的链表组合起来形成符合要求的新链表。
  （2）API Contract来源于在思考（1）问题时解决原问题需要的信息。例如在LC114中，可以发现假设解决了子问题后只返回root结点是不够的，这时候我们需要让它返回flatten后的tail结点方便左右子树同时存在时的处理。

我自己觉得这个思维模式不仅适用与递归方法也同样适用于DP之类的其它题型。大家觉得有用的话请加加米啦。还是有很多帖子没有米看不了，谢谢大家。如果还有什么问题欢迎留言一起探讨。

从另一个角度看递归的本质：信任

Let’s trust the process

还有一个小tip: solve或者debug 递归的时候，大忌就是去人脑压栈，去一层层往下再往上的套，这样非常容易就乱了。就想前面几楼说的, trush the process。相信子问题是一个已经被解决的状态，怎么通过这个子问题来解决当前问题。最后base case也就是结束条件搞清楚了就完全没问题了。LC的各种backtracking，tree的dfs几乎都是这样的套路。

我的方法是套模板 常规的dp 无外乎 array上一维O(n)或者二维O(n2) 甚至再在ij中间再遍历一一遍k  
或者就是以某个数值为cut off 找答案 然后遍历 找min/max等等
或者就是dfs再加上记忆化 这个从前往后推 更容易

我一般都是套模板 看哪个模板能用 只要模板找对了  基本这个题就一马平川了

做dp时 我个人一直强迫自己要想high level 不要想细节

谢谢分享，码住

感谢分享，收藏

明确记住本层的问题是什么，只考虑本层，剩下的交给字问题处理。

qiuqiushasha 发表于 2020-11-24 12:18:42
我的方法是套模板 常规的dp 无外乎 array上一维O(n)或者二维O(n2) 甚至再在ij中间再遍历一一遍k  
或者就是以某个数值为cut off 找答案 然后遍历 找min/max等等
或

强迫想high level很重要，接口定义好后所有的都是implementation detail可以放在后面想。一些层次比较清晰的题每一步不光接口可以很清晰，时间空间复杂度也可以很清晰。

码了 谢谢分享

楼主这题刷的确实有意义