n樓梯的最大步驟數

這是一個家庭作業問題，它是DP，但它不是'有多少種方法可以達到第n個樓梯問題'。n樓梯的最大步驟數

相反，在這個問題中，每個樓梯臺階被分配一個從-10000到10000的數字，例如，我有如-1 2 1的步驟，我必須找到最大的總和，同時能夠每步上一步或跳過一步。在那個例子中，答案是3，因爲我可以跳過第一步，然後只是訪問其餘的樓梯。

我注意到，我總是可以刪除最後一步，因爲無論如何我必須踩到它。

我該如何在動態編程方式下做到這一點？我在每一步中找到最大的總和？

來源

2015-06-02 maregor

動態編程，你知道的全是關於問正確的問題。

問題應該問這裏有一個例子：

A = [-5，-2,1，3]

什麼是最大值，你可以得到，如果你踩了2步（數組索引從零開始），其值是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]）的

來源

2015-06-02 20:34:00

'F [N] = A [N] +最大（F [n-1]，F [n-2]）'是對等式的簡化。 – Dukeling

只是線索：

假設你想達到第n步。你可以從步驟n-2或n-1進行。

所以F（N）= MAX（F（N-2），F（N-1））+ X [N]

來源

2015-06-02 05:44:52 ElKamina

除了ElKamina的回答，請記住，不管你選擇在任何做舞臺（前進一步或兩步），從那裏的第三項是可達...

來源

2015-06-02 14:52:42

設置一個整數數組（或長或任何將保存加或減10000 * n）稱爲sum[n]，可能的最大總和如果你站在步驟n。請注意，sum[0]=step[0]是給出的數組的第零個元素，但sum[1]= max{0+step[1],sum[0]+step[1]}因爲您可以直接從地板到達第1步或者通過第零步。現在找出sum[2]的類似公式，並進行推廣。然後按順序計算sum[i]。

我不認爲你可以「刪除最後一步」。您可能必須踩下它，並且可以避免它，無論什麼最好。不過，您可能想引入一個虛假的值爲0的最後一步。

來源

2015-06-02 17:54:25

n樓梯的最大步驟數

回答

相關問題