kmp算法是否属于动态规划？
来源：1-1 算法面试不仅仅是正确的回答问题
哈哈哈蜜瓜
2020-02-04
在网上看到一条KMP题解，里面说到KMP是动态规划算法，但我以前问过动态规划的无后效性问题，简单总结无后效性要么是后者的状态对前者的状态有多种选择，要么就是后者的状态是不可改变的。但是KMP的核心是后缀找相同前缀，那么状态也就只能定义成某个字符有多少个相同前缀，所以状态是单一可变的，所以我个人看法是KMP并不属于动态规划，不知道是否理解有误，有的话请bobo老师指出：）
写回答
1回答
-
kmp 算法分成两部分。
第一部分是求解一个辅助的匹配数据结构，比如你说的题解中，无论是求解 next 数组还是求借这个 dfa，都是这部分。这部分可以理解成动态规划。
第二部分是具体的利用这个辅助数据做匹配，这部分不是动态规划。
不过整体，通常不会把 kmp 和动态规划联系起来。说实话，将这种经典算法和算法思想联系起来，是挺虚的，我个人认为并不有助于理解经典算法本身。比如 Prim 算法背后有贪心的思想，但是了解这一点并不会让你对 Prim 理解的更深刻；Dijkstra 背后既有贪心的思想，又有动态规划的思想，同样，我不认为了解这一点会让你对 Dijkstra 理解的更深刻：）
继续加油！：）
132020-02-06
相似问题