算法与数据结构

TODO 数据结构基础知识 数据结构是什么，其特性有缺点，使用场景，基础使用等等

TODO 算法的基础使用，优缺点，使用场景，底层逻辑，时间空间复杂度分析等等

数据结构

常见数据结构与算法整理总结(上)

算法

迭代法

关键点:

• 将一个原问题修改为子问题
• 对子问题重复调用计算
• 特性：
  • 重复计算多，耗时高，时间复杂度高

动态规划

• 关键点:
  • 将一个原问题修改为子问题
  • 试图只解决每个子问题一次，一旦其问题已经解决，会将其存储，从而避免重复计算
  • 特性:
    • 尽量避免重复计算，时间复杂度低。
• 关键概念
  • 最优子结构
  • 边界
  • 状态转移公式

# 动态规划 存储计算中值，减少计算量
def fun(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    a = 1
    b = 2
    tmp = a + b
    for i in range(3, n):
        tmp = a + b
        a = b
        b = tmp
    return tmp
# 迭代法
def fun(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return fun(n-1) + fun(n-2)

f(10) = f(9) + f(8) 是【最优子结构】
f(1) 与 f(2) 是【边界】
f(n) = f(n-1) + f(n-2) 【状态转移公式】

相关资源

• ★★★★★ TODO 五分钟学算法：算法与数据结构文章详细分类与整理！
• 图解 递归与动态规划