algorithm - 启动时以最小的能量到达目的地

在与原点距离的直线上给定N个点同时，我们也得到了我们需要到达的终点。现在到了第i点，我们应该有X[i]数量的能量，而且这一点也会给Y[i]数量的利润，作为能量被添加现在我们需要找出我们应该从多少最小能量开始，以便在从原点出发后到达目的地。
例：我们有5个点，目的地距离原点10个单位。
然后我们假设第一个点是从原点算起的1个单位，需要2个单位的能量，得到3个单位的利润。
第二点是从原点出发2个单位，需要3个单位的能量，利润为0个单位。
第三点是从原点算起的4个单位，需要3个单位的能量，利润为5个单位。
第四点是从原点算起8个单位，需要5个单位的能量，利润为0个单位。
第五点是从原点算起的9个单位，需要1个单位的能量和2个单位的利润。
现在这个配置的答案是6。
说明：
因为如果我们从5个单位的能量开始
在点1，我们有多于或等于2个单位的能量，因此利润1加上能量，总能量是6。
在第二点，三个单位的能量会消失，只剩下三个单位。
在第3点，由于能量正好是3，利润将被增加，总能量变成5。
在第4点，所有5个单位都将消失，我们无法前进
类似地，如果我们从6开始，其中一个将能够通过点4到达点4，在那里它将增加一个能量单位，我们将到达目的地
现在我们要找到到达最终目的地所需的最低能量。

最佳答案

您已将问题标记为动态编程但我认为这更多的是一个用简单的O（n）解决方案解决的临时问题从反面开始解决问题对于n=5分的给定问题：
要到达目的地，在第5点必须至少有1个能量单位现在假设您输入第五个能量单位为x的点，然后您可以通过方程式找到x的最小值：
x-1+2>=1
意味着x>=0
但x的最小值应该是1，才能达到第5点因此x=1。
所以当你进入第五点到达最终目的地时，你必须至少有1个单位的能量。同样地，我们可以找到进入第四点所需的最小能量值，如下所示：
X-5+0>=1
意味着x>=6
因此，要到达目的地，当你进入第4点时至少需要6个能量单位。
以这种方式继续，你可以找到当你进入第一个点时所需要的最小能量。这将是必要的答案。
以下working java code实现了这一点：

        for(int i=0; i<n; i++){
            req[i] = sc.nextInt();
            profit[i] = sc.nextInt();
        }

        int minReq = 1;
        for(int i=n-1; i>=0; i--){
            int minEnter = minReq+req[i]-profit[i];
            minEnter = Math.max(minEnter, req[i]);
            minReq = minEnter;
        }

        System.out.println(minReq);

关于algorithm - 启动时以最小的能量到达目的地，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29326620/