斐波那契數列是動態規劃問題嗎？

-3

* probl =問題。我在說計算第n個斐波納契數的問題。這裏的一些用戶說這實際上是一個DP問題（請看這個問題的第一個答案和相同回答的評論What is dynamic programming?），但其他人說這不是因爲它沒有優化任何東西，而是因爲其他原因，不是嗎？斐波那契數列是動態規劃問題嗎？

來源

2014-07-25 carl

這個問題似乎是題外話，因爲它不是關於編程。 – duffymo

有一個簡單的代數公式來計算任何斐波納契數值，所以不需要「動態」程序：http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression –

我假設「dp」意思是「動態編程「。如果是這樣的話，那麼是的。這是一個編程問題。這不是一個很好的。原始海報需要爲他的家庭作業執行他自己的分析。當然，這是他的導師對他的期望。 –

從Wikipedia頁面動態規劃，

var m := map(0 → 0, 1 → 1) 
function fib(n) 
    if key n is not in map m 
     m[n] := fib(n − 1) + fib(n − 2) 
    return m[n] 

This technique of saving values that have already been calculated is called memoization; this is 
the top-down approach, since we first break the problem into subproblems and then calculate and 
store values.

所以，它是用來獲取序列中的第N號的技術之一。

編輯 - 對於添加的問題，memoization是DP的一種形式。

來源

2014-07-25 17:19:28 Swapnil

感謝您的回覆。但是你正在使用DP技術來解決這個問題，但是這樣做是否會導致Fib。系列DP問題？ – carl

沒有什麼像DP問題。使用這種技術可以解決的問題可以稱爲DP問題。如果你願意，你可以稱之爲DP問題。但許多DP問題也有非DP解決方案。 – Swapnil

斐波那契數列是動態規劃問題嗎？

回答

相關問題