数据结构与算法的刷题笔记

如何审题

判断题目的类型
- 动态规划
  - 一般都是子数组，子序列的查找
- 排序
- 二叉树
- 堆栈队列链表
快速像一个baseline，
- 比如快速想一个暴力求解的思路，判断时空复杂度
  - 一种是直接来几个for循环
  - 一种是拆成递归
  - 双指针
- 确定好解题的结构
  - 边界值判断
  - 递归结构
    - 子问题求解
    - 子问题结果融合
  - 结果返回
然后优化
- 寻找重复计算的结构，空间换时间
  - 存储中间计算结果
- 设置好边界条件，省去不必要的计算

动态规划

能用动态规划求解的问题特点
- 具有最优子结构
- 无后效性
解题步骤
- 拆解出子问题
- 确定子问题的状态
- 确定初始状态
- 确定状态转移方程
常用形式
- 递归
- 递推