use*_*840 3 algorithm graph directed-acyclic-graphs
我在"Hitchhiker的算法指南"中读到了这个陈述.但是,我无法将其可视化为LIS问题,我们所拥有的只是一系列数字.如何将其调整为图形问题？
想象一下2D网格的问题.你在左下方的广场,你需要到达右上方.你能想象出这个计划中的非循环DAG吗？
现在想象一些广场是被禁止的.禁止使用正方形可能会导致"锁定"(您可能会发现自己陷入困境),现在选择要遵循的路径实际上非常重要.在图形方面,您可以将禁止正方形视为删除顶点,并且您的目标是从根到一个特定节点(接收器).
现在让我们回到LIS.在解决LIS问题时,您实际需要做的是决定选择哪些数字,哪些数字不是.限制是,无论何时选择一个号码,您都不能选择任何小于此号码的号码(您按顺序选择号码).
现在我们可以混合两种东西.想象一下,你将从你的数字序列中构建一个图形:
此图表上的每个路径都是有效的增加子序列.找到LIS的问题现在是在该图上找到最长路径的问题.