Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

邓俊晖 数据结构 1.绪论（下） #42

Open
xxleyi opened this issue Mar 17, 2019 · 25 comments
Open

邓俊晖 数据结构 1.绪论（下） #42

xxleyi opened this issue Mar 17, 2019 · 25 comments
Labels
WHAT

Comments

@xxleyi
Copy link
Owner

xxleyi commented Mar 17, 2019

image
@xxleyi
Copy link
Owner Author

xxleyi commented Mar 17, 2019

image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 17, 2019

image
image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 17, 2019

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 17, 2019 •
edited
Loading

image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 17, 2019

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image
image
三生三世中的一天，也就是一天中的一秒
image
整个宇宙中的三生三世，相当于三生三世中的 0.1s

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019 •
edited
Loading

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019 •
edited
Loading

面试常见

image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

几何级数与末项同阶

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019 •
edited
Loading

面试常见

image
image
image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

image
image
image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019

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

image

@xxleyi xxleyi added the WHY label Mar 18, 2019
@xxleyi
Copy link
Owner Author

xxleyi commented Mar 18, 2019 •
edited
Loading

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

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

递推方程：
image

封底估算：
image
image
image

递归实例：
image
上台阶类比：一次走一个或两个台阶
image

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

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

image

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

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 19, 2019 •
edited
Loading

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

image
image
image
image
leap of faith in recursion
image

理解

image

image

颠倒次序之后的迭代

image

@xxleyi
Copy link
Owner Author

xxleyi commented Mar 19, 2019

总结

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

@xxleyi xxleyi added 有看头 and removed WHY labels Mar 19, 2019
@xxleyi
Copy link
Owner Author

xxleyi commented Mar 28, 2020

补充

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

@xxleyi xxleyi added WHAT and removed 有看头 labels Mar 28, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
WHAT
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@xxleyi