動態規劃算法

我會通過這本教科書試圖解決一些算法改善自己的技能，我目前停留在這個問題：動態規劃算法

本章是動態規劃和我因爲我不知道如何處理這些類型的問題，所以我只是在解決問題時遇到了麻煩。任何人都可以幫我解決它或指向我現有的算法是類似的？

2013-10-18 user2836553

通常與DP一個有用的第一步是，違反直覺，使問題更*特定：你可以計算你可以得到的最大數量的冰棍*從某天給我*開始？（重要提示：通知我說「從第一天開始」，而不是「從第一天開始，接受當天的棒棒糖」，即使你在第一天開始，你仍然可以選擇等待一天或多天）。（一世）。你能用f（）的其他值來爲f（i）寫一個表達式嗎？提示：它必須是您在第一天可以做出的最大選擇...... –

您需要哪種編程語言解決方案？ – necromancer

答案不一定要用任何語言。算法僞代碼解決方案將會很好。 – user2836553

的解決這個問題的是下面的遞歸公式的溶液：

f(i) = max{ l_i + f(i+k_i) , f(i+1) } 
f(x) = 0 : for all x > n

對於問題的解決方案是f(1)溶液。

說明：對於每一天，您可以「跳過」這一天，並檢查第二天（或之後的一個，...，這是通過調用f(i+1)完成的） - 或採取棒棒糖，然後你可以選擇在k_i天后才能返回 - 這意味着您添加了f(i+k_i)的解決方案。

來源

2013-10-18 22:37:00 amit

動態規劃算法

回答

相關問題