邓俊晖 数据结构 1.绪论（下） about learning_list HOT 25 OPEN

from learning_list.

from learning_list.

from learning_list.

from learning_list.

from learning_list.

from learning_list.

from learning_list.

三生三世中的一天，也就是一天中的一秒

整个宇宙中的三生三世，相当于三生三世中的 0.1s

from learning_list.

from learning_list.

from learning_list.

from learning_list.

from learning_list.

from learning_list.

from learning_list.

面试常见

from learning_list.

from learning_list.

几何级数与末项同阶

from learning_list.

from learning_list.

面试常见

from learning_list.

from learning_list.

动态规划：DSA 设计与优化的法宝，递归找思路，迭代找效率

from learning_list.

fab 数列的优化之路（面试常见）

从第零项开始，0 和 1 是平凡情况，之后依次取最后两项之和，呈现独有一套独有数列。

递推方程：

封底估算：

递归实例：

上台阶类比：一次走一个或两个台阶

ipython 中 fab?? 直接得到source code:

def fab(n):
    return n if n < 2 else (fab(n-2) + fab(n-1))

def fab(n):
    cache = {}
    def _fab(n):
        if n in cache:
            return cache[n]
        cache[n] = n if n < 2 else (_fab(n-2) + _fab(n-1))
        return cache[n]
    return _fab(n)

def fab(n):
    f, g = 0, 1
    if n < 2:
        return n
    while n > 1:
        f, g = g, f + g
        n -= 1
    return g

from learning_list.

最长公共子序列（面试常见）

leap of faith in recursion

理解

颠倒次序之后的迭代

from learning_list.

总结

• 迭代、递归、动态规划：DSA 设计与优化的全部法宝
• 对于某些在直觉上不好迭代求解的问题，可以先进行逆向递归求解
  • 递归求解的关键
    • 递归基
    • 信念飞跃(leap of faith)
• 递归求解方案的正确性得到验证之后，分析整个递归过程，然后设计反向迭代算法

from learning_list.

补充

贪婪和回溯可以视为动态规划的特例

from learning_list.