CS 97SI 内容总结

参考自斯坦福 CS 97SI 课程

2.数学

• 2.1 代数
• 2.2 数论
• 2.3 组合数学
• 2.4 几何

3.数据结构

• 3.1 树状数组（Fenwick tree）: 用于查询变化的数组中的前缀和，查询和更新时间都是 O（logn），构建一个Fenwick Tree 需要O（nlogn）
• 3.2 线段树（Segment Tree）：用于在变化数组中快速查询区间累计的结果，sum/max/min等

4. 动态规划

DP is simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner
DP 通过记忆化的方法仅求解一次大量重复的子问题，达到比朴素算法大大减少计算复杂度的目的 —Wikipedia

DP的适用情况：

• 最优子结构：如果一个问题可以递归地分解，并且全局的最优解由子问题的最优解组成，那么就说这个问题有最优结构，有最优结构的问题可以使用动态规划进行求解。
• 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
• 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，

步骤：对于一个有最优子结构的问题，我们通过一下方法进行求解：

1. 定义子问题：找到什么样的问题是有相同结构并重复出现的
2. 找到大问题和子问题之间的联系
3. 找到子问题的最优解

• 一维动态规划
• 二维动态规划
• 间隔动态规划(Interval DP）
• 树动态规划