爬坡问题需要动态编程

本文介绍了爬坡问题需要动态编程的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

因此，基本上，问题是有一系列山丘点.我们只能从一个山点移动到下一个更大的山点.

请查看下图以了解想法.

在上面的图像中，黑点是山顶，每个山顶上都有一些带有一定口味价值的香料.我们可以从一个山顶移到另一个山顶，品尝其中的香料.

请参阅下图以了解有效的移动.绿线给出有效的移动.

因此，现在我们将得到一个包含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的持续时间是否有可能.

如果路径是可行的，而不是如何在恒定时间内计算路径的总和.

解决方案

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

要将问题转换为这种形式，请为每个山峰定义一个节点，然后让节点的父节点成为我们可以从此处移动到的山峰.引入一个额外的根节点，该节点是没有有效移动的任何山丘的父级.

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

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

一开始似乎很难构建图形，但是也可以使用下一个更大元素算法.

So, basically the problem is that there is a series of hill points. we can only move from one hill point to the next greater hill point.

Please see the below image to get an idea.

On above image black points are hill tops, each hill top has some spices with some taste value. we can move from one hill top to another tasting spices in them.

Please See below image to know valid movements. green lines gives valid movements.

So, Now we will be given a query with 2 integers b,c and for each query we need to find if moving from b hill point to c is possible. if it is then we have to output the total tastiness of journey.

Suppose a query comes in which b = 1 , c = 10.

So we need to find if moving from hill 1 to hill 10 possible and if it is we have to output the tastiness of journey.

The problem is simple if there are very low queries, as for each query we can just iterate in loop and find if reaching from 1 to 10 is possible or not and if it is then we will sum the taste.

for this particular problem our path will be 1-->2-->6-->7-->9-->10.

But if a query comes such that b = 1 , c = 11.

so we cant go from 1 to 11, hence no path is possible and answer is -1.

But when there are very large queries we can iterate in loop for every query. I mean we have to pre-process the data, so that in each query we just calculate the result in constant time.

What particularly i want to know ?

How can i know if reaching from b to c is possible or not in constant time.

If path is possible than how to calculate the sum of path in constant time.

解决方案

You can solve this with O(n) space and O(n+q) time where q is the number of queries using a lowest common ancestor algorithm. Here is a topcoder algorithm tutorial that explains the algorithm.

To convert the problem into this form, define a node for each hill, and let the parent of a node be the hill we can move to from this point. Introduce one extra root node that is the parent of any hills that have no valid move.

Then to determine if there is a path from b to c, you simply check whether LCA(b,c) is equal to c.

You can also precompute in O(n) the sum of spices on a path starting at each node and ending at the root node. To compute the sum along a path, you simply subtract the sum starting at c from the sum starting at b.

It may seem a bit hard to construct the graph in the first place, but this can also be done in O(n) using a next greater element algorithm.