1. KMP算法字符串匹配的利器第一次接触KMP算法时我被它的精妙设计深深震撼。相比暴力匹配方法KMP通过预处理模式串将时间复杂度从O(mn)优化到O(mn)。这就像在茫茫人海中找人暴力匹配是一个个问过去而KMP则像拿着地图直接定位。核心在于next数组的构建。我刚开始总把next数组理解成前缀和后缀的最长公共部分后来发现更准确的说法是当匹配失败时模式串应该回退到什么位置。举个例子对于模式串ababcvoid buildNext(const string pattern, vectorint next) { next[0] -1; int i 0, j -1; while (i pattern.size()) { if (j -1 || pattern[i] pattern[j]) { i; j; next[i] j; } else { j next[j]; } } }实际匹配时主串指针永不回退这个特性让KMP在处理大文本时优势明显。记得有次处理百万级日志文件暴力匹配直接卡死换成KMP后秒级完成。2. Dijkstra算法最短路径的经典解法Dijkstra算法是解决单源最短路径问题的标杆算法。我第一次实现时犯了个典型错误——没处理负权边结果程序给出了错误答案。后来才明白Dijkstra的贪心性质决定了它只适用于非负权图。朴素版本适合稠密图时间复杂度O(n²)。核心思想是维护两个集合已确定最短距离的顶点集合S和未确定的集合T。每次从T中选取距离起点最近的顶点加入S并松弛其邻接边。void dijkstra(int src) { vectorint dist(n, INF); dist[src] 0; vectorbool visited(n, false); for (int i 0; i n; i) { int u -1; for (int j 0; j n; j) { if (!visited[j] (u -1 || dist[j] dist[u])) u j; } if (dist[u] INF) break; visited[u] true; for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; } } } }堆优化版本将时间复杂度降到O(mlogn)适合稀疏图。这里有个坑STL的priority_queue不支持修改优先级所以同一个顶点可能被多次加入堆。需要通过visited数组过滤。3. 动态规划从背包问题入门动态规划(DP)是算法学习的分水岭。我最初被各种状态转移方程绕晕直到从背包问题入手才豁然开朗。01背包是DP的经典入门问题它的状态定义非常典型f[i][j]表示前i件物品放入容量为j的背包的最大价值。二维实现直观易懂for (int i 1; i n; i) { for (int j 0; j m; j) { f[i][j] f[i-1][j]; if (j v[i]) f[i][j] max(f[i][j], f[i-1][j-v[i]] w[i]); } }优化到一维时需要特别注意遍历顺序for (int i 1; i n; i) { for (int j m; j v[i]; --j) { f[j] max(f[j], f[j - v[i]] w[i]); } }完全背包与01背包的区别仅在于遍历顺序正向遍历for (int i 1; i n; i) { for (int j v[i]; j m; j) { f[j] max(f[j], f[j - v[i]] w[i]); } }4. 动态规划进阶线性与区间DP线性DP中最经典的莫过于最长上升子序列(LIS)。朴素解法O(n²)的思路是f[i]表示以a[i]结尾的LIS长度需要遍历之前所有元素for (int i 0; i n; i) { f[i] 1; for (int j 0; j i; j) { if (a[j] a[i]) { f[i] max(f[i], f[j] 1); } } }优化版本O(nlogn)利用贪心二分查找维护一个单调递增的数组qq[i]表示长度为i1的LIS的最小末尾值。区间DP的代表问题是石子合并。f[i][j]表示合并第i到第j堆石子的最小代价需要枚举分割点kfor (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; f[i][j] INF; for (int k i; k j; k) { f[i][j] min(f[i][j], f[i][k] f[k1][j] s[j] - s[i-1]); } } }这种三重循环的结构是区间DP的典型特征。我在做这类题时会先在纸上画出区间分割示意图帮助理解状态转移过程。