图分层与DP

Question

图分层是处理具有一定限制的最短路径的一种常用技术。下面是关于这种技术的描述：M?t=47m7s。所以，只是想知道，这个技术是否和做DP一样，但是只是有一个不同的记忆结构？

Answer 1

最短路径算法已经是动态规划算法。它们根据节点前辈的最短路径(最优子结构)计算节点的最短路径，并回传每个节点的结果，因为每个节点都可以是几个不同的后续节点的前身(重叠子问题)。

“分层技术”允许您扩展动态编程解决方案，以处理限制和其他复杂问题。