arrays - 需要动态规划的爬山问题

Question

所以，基本上问题在于存在一系列山点。我们只能从一个山点移动到下一个更大的山点。

请看下面的图片来了解一下。

上图中黑点是山顶，每个山顶都有一些具有一定味道的香料。我们可以从一个山顶移动到另一个山顶，品尝其中的香料。

请参阅下图了解有效 Action 。 绿线给出了有效的 Action 。

所以，现在我们将得到一个包含 2 个整数 b、c 的查询，对于每个查询，我们需要确定是否可以从 b 山点移动到 c。如果是，那么我们必须输出旅程的总味道。

假设有一个查询 b = 1 , c = 10。

因此我们需要确定是否可以从山 1 移动到山 10，如果可以，我们必须输出旅途的美味。

如果查询非常少，问题就很简单，对于每个查询，我们可以循环迭代，看看是否可以从 1 到 10，如果可以，我们将对味道求和。

对于这个特定问题，我们的路径是 1-->2-->6-->7-->9-->10。

但是如果查询出现时 b = 1 , c = 11。

所以我们不能从 1 到 11，因此没有路径是可能的，答案是 -1。

但是当有非常大的查询时，我们可以为每个查询循环迭代。我的意思是我们必须对数据进行预处理，以便在每个查询中我们只需在恒定时间内计算结果。

我特别想知道什么？

我如何知道是否可以在常数时间内从 b 到达 c。

如果路径是可能的，那么如何在常数时间内计算路径的总和。

Answer 1

您可以使用 O(n) 空间和 O(n+q) 时间来解决此问题，其中 q 是使用最低公共(public)祖先算法的查询数。这是一个 topcoder algorithm tutorial这解释了算法。

要将问题转化为这种形式，为每个山丘定义一个节点，并让节点的父节点为我们可以从该点移动到的山丘。引入一个额外的根节点，它是任何没有有效移动的山丘的父节点。

然后要确定是否存在从 b 到 c 的路径，您只需检查 LCA(b,c) 是否等于 c。

您还可以在 O(n) 中预先计算从每个节点开始到根节点结束的路径上的香料总和。要计算一条路径上的总和，只需从从 b 开始的总和中减去从 c 开始的总和。

首先构建图形似乎有点困难，但这也可以使用 next greater element algorithm 在 O(n) 中完成.