algorithm - n 阶梯的最大步数和

Question

这是一道作业题，是DP，但不是'有多少种方法可以到达第n阶梯的问题'。

相反，在这个问题中，每个楼梯台阶都被分配了一个从 -10000 到 10000 的数字，例如我有-1 2 1这样的步骤，我必须找到最大的总和，同时每次都能上一步或跳过一步。在该示例中，答案是 3，因为我可以跳过第一步，然后只访问其余的楼梯。

我注意到我总是可以删除最后一步，因为无论如何我都必须踩到它。

我怎样才能以动态编程的方式来做这件事？我是否找到了每一步的最大总和？

Answer 1

如您所知，动态编程就是提出正确的问题。

这里应该问的问题有一个例子:

a = [-5, -2, 1, 3]

如果你踩到值为1的2步(数组索引从零开始)，你能得到的最大值是多少？

让我们将 f[2] 定义为您在 2 步之前可以获得的最大值。所以你在那里有选择；要么踩，要么不踩。

If (step on 2 step in array index i.e 1)
    you can also step on previous step i.e -2 or skip the previous step
    if (you skip the previous step i.e -2)
        you need to step on previous to previous step i.e -5

从上面可以看到

   f[2] = max(a[2] + a[1] or a[2] + a[0])

我也在学习，不知道下面说的对不对？

F[n] =max(F[n-1]+a[n], F[n-2]+a[n])