algorithm - 计算所有双音路径

Question

我正在尝试计算一组给定点的所有双调路径。

给定N分。

我的猜测是有 O(n!) 条可能的路径。

推理

您可以从起始位置选择 n 个点。从那里你有 n-1 点，然后是 n-2 点......这似乎等于 n!。

这个推理正确吗？

Answer 1

你可以用很好的旧动态规划来解决它。

令 Count(top,bottom) 为不完整旅行的数量，其中 top 是最右边的顶行点，bottom 是最右边的点，top 和 bottom 左边的所有点都已经在路径中。

现在，Count(i,j) = Count(k,j) 其中 k={i-1}U{l: l

这是 O(n^3) 的复杂度。

如果你想枚举所有的双调路径，用 Count 也可以跟踪所有的路径。在更新步骤中适本地附加路径。但是，这将需要大量内存。如果你不想使用大量内存使用递归(同样的想法。对点进行排序。在每个递归点要么将新点放在顶部 fork 或底部 fork 并检查是否有任何交叉)