状态转移

给定一棵二叉树，找出其直径——这条路径可能穿过根节点，也可能完全在某个子树中。当你第一次看到 LeetCode 543 这道题时，可能会想：从根节点出发，找到最深的左节点和最深的右节点，把两条路径连起来不就是答案吗？但这个直觉会出错——直径可能根本不经过根节点。 ...

当你第一次尝试实现斐波那契数列时,可能会写出这样的递归代码: public int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } 这段代码看起来简洁优雅,但当 n 达到 50 时,程序会运行很长时间才能返回结果。问题出在哪里?重复计算。计算 fib(5) 时会调用 fib(3),计算 fib(4) 时又会再次调用 fib(3)。随着 n 增大,重复计算的次数呈指数级增长——时间复杂度高达 $O(2^n)$。 ...