动态规划 内容部分来自：什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 阮行止的回答 - 知乎 Widely-known Definition 无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。 最优子结构：大问题的最优解可以由小问题的最优解推出。 使用动态规划的条件：能将大问题拆成几个小问题，且...

DFS 搜索树：由状态构成的树状结构 DFS：深度优先遍历搜索树。使用栈存储历经的路径，故使用空间$O(h)$；而BFS可能使用$O(2^h)$的空间，故一般使用DFS占空间较小。 对于状态信息的存储，可在函数局部（栈中）存储，也可在全局存储（全局变量）： 可使用全局变量存储回溯时易于恢复现场的信息，同时在状态转移时免于频繁复制（适合数组类） 可使用局部变量存储回溯时不方便...

时间复杂度：渐近分析 见《算法导论》第三章 算法运行时间影响因素 算法运行时间受多因素的影响： 机器性能（指令执行速度 = IPC * 时钟频率）、编程语言效率、数据规模、数据特点，以及算法本身。 对算法竞赛来说，如果不考虑卡常，主要考虑后三者。 根据数据特点分 考虑数据的不同特点，可以考虑最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度。 渐近记号 只考...

单链表 有两种实现方式： 结构体实现 数组模拟 两者在功能上实际上是等价的，但后者比前者代码更简洁。前者使用真正的指针来引用节点，后者使用数组索引来引用节点。后者实际上相当于用数组索引“模拟”了一个地址空间。将数组定义为全局变量，因此也无需在运行时频繁申请空间。 应用： 存储图、树的邻接表 const int N = 100010; int head, e[...

快速排序 步骤： 随机取一元素“pivot” 划分区间 递归对左右区间进行快速排序 void quick_sort(int q[], int l, int r){ if (l>=r) return; int x=q[(l+r)/2], i=l-1, j=r+1; while (i<j) { do i++; while ...