图分层和DP

Question

图分层是处理最短路径的常用技术，但有一些限制。以下是关于此技术的描述：https://youtu.be/OQ5jsbhAv_M?t=47m7s。所以，只是想知道，这种技术是否与做 DP 一样，只是记忆结构不同？

Answer 1

最短路径算法已经是动态规划算法了。他们根据到其前任节点的最短路径（最优子结构）计算到一个节点的最短路径，并为每个节点记住结果，因为每个节点都可以是几个不同后继节点的前任节点（重叠子问题）。

"layering technique" 允许您扩展动态规划解决方案以处理限制和其他类型的复杂情况。