n 阶梯的最大步数和

Question

这是一道作业题，是DP，但不是'how many ways are there to reach the nth-stair problem'。

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

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

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

Answer 1

一点线索：

假设您要进行第 n 步。您可以从第 n-2 步或第 n-1 步开始。

所以 F(n)=Max(F(n-2),F(n-1)) + x[n]

Answer 2

除了 ElKamina 的回答之外，请记住，无论您在任何阶段（向前或向前迈出一步）选择做什么，都可以到达第三项...

Answer 3

设置一个名为 sum[n] 的整数数组（或长整数或任何可以容纳正负 10000*n 的数组），如果您站在台阶 n 上，则可能是最大的总和。请注意，sum[0]=step[0] 是给定数组的第零个元素，但 sum[1]= max{0+step[1],sum[0]+step[1]} 是因为您可以直接从地板或通过第零步到达第 1 步。现在找出 sum[2] 的类似公式并进行概括。然后依次计算sum[i]。

我不认为你可以"remove the last step"。你可能不得不踩它，你可以避免它，最好的。不过，您可能想引入一个值为 0 的假最后一步。

Answer 4

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

这里应该问的问题和例子：

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

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

让我们定义 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])

n 阶梯的最大步数和

Biggest sum of steps for n stairs

algorithm

dynamic-programming