我在“Hitchhiker's guide to algorithms”中读到了这句话。但是，我无法将其可视化，因为在 LIS 问题中我们所拥有的只是一个数字序列。如何将其调整为图形问题？
最佳答案
想象一下二维网格的问题。你在左下角的方 block 上，你需要到达右上角的方 block 。你能想象出这个方案的非循环 DAG 吗？
现在想象一些方 block 是禁止的。禁止正方形可能会导致“锁定”(您可能会发现自己被困)，现在选择要遵循的路径实际上很重要。 在图形方面，您可以将禁止方 block 视为删除顶点，您的目标是从根节点到一个特定节点(汇点)。
现在让我们回到 LIS。在解决 LIS 时，您实际需要做的是决定您将选择哪些数字，以及您不会选择哪些数字。限制是无论何时你选择一个号码，你都不能选择比这个号码更小的号码(你按顺序选择号码)。
现在我们可以混合使用这两种东西。想象一下，您将根据数字序列构建一个图形:
- 每个数字都是一个节点。
- 数字节点 A 有一条边到数字节点 B 当且仅当
- B 在序列中排在 A 之后
- B 的值(value)大于 A
- 有一个特殊的节点end
- 每个节点都有一条边到end
此图上的每条路径都是有效的递增子序列。寻找 LIS 的问题现在是寻找这张图上的最长路径的问题。
关于algorithm - 最长递增子序列如何成为 DAG 中最长路径的特例？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12907106/