动态规划经典题目(三):最长公共子序列(LCS)

最长上升子序列和最长公共子序列两篇博客都是为了后面的最长公共上升子序列准备啊~

一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则它就是这两个序列的最长公共子序列(Longest Common Sequence,简称LCS)

继续阅读“动态规划经典题目(三):最长公共子序列(LCS)”

SPFA算法总结

SPFA真是最好的单源最短路算法,没有之一。

SPFA全称是Shortest Path Faster Algorithm,直译过来就是“最短路更快算法”,从这个名称就能看出SPFA效率很高。SPFA加上SLF优化以后被称作单源最短路的“无敌”,时间复杂度可以达到O(ke)(k表示平均每个节点入队次数,k≤2,e表示边数),可以刷负边权。

继续阅读“SPFA算法总结”