1樓：鄧哥不是燉鍋
個人理解：
遞迴：當前時刻的 的解一定來自於上一時刻
DP：當前時刻的 的解可能來自於前面任意時刻大部分時候，DP和帶記憶的遞迴效果相同。當DP每個時刻都只依賴於前一時刻的最優解時，DP退化為貪心法
2樓：
多讀書。讀好書。
參考《演算法導論》中的動態規劃篇章。不懂就該找書看。
演算法是演算法，實現是實現。這是兩碼子事。區別就是他們都不是一類東西，處處都是區別。
動態規劃是用來解決一類問題的演算法。與之做對比的是貪心。這類東西是需要嚴格證明的，且這些問題有一些特定的特徵。
動態規劃的本質是空間換取時間，把需要的資訊先存起來供後面計算使用。
所以，動態規劃的實現可以是自頂向下的帶備忘的遞迴，也可以是自底向上的迴圈。這都是等價的兩種形式而已，複雜度都一樣，可能就是係數的話自底向上的實現形式稍微小一點，所以動態規劃的實現一般採用自底向上的形式。但這是實現層面的東西。
跟演算法本身沒啥關係。
而遞迴是程式設計方式，函式自己呼叫自己，比如乙個樹狀結構就可以用遞迴搭配回溯來實現遍歷。動態規劃可以用遞迴來實現。
結論是，動態規劃和遞迴的區別是他們不是一類東西無法做區別。你要問聯絡的話，那就是動態規劃可以用遞迴來實現。
書上的內容我就不貼了。自己找去。
3樓：TzzT
很多遞迴可以改成動態規劃，基本所有的動態規劃都可以改成遞迴。這兩個之間有乙個很重要的區別，遞迴可能會多次計算已經算過的值，而動態規劃則一般通過陣列等容器將算過的值直接儲存起來，算過的值就不用再算一遍了。這個差別使得動態規劃會比遞迴快很多，因為省掉了很多重複的計算。
4樓：偉大的車爾尼
這兩個術語是不同的概念。動態規劃屬於演算法領域，其思想是拆分問題，利用子問題的解（區域性最優解）得到原始問題的解（全域性最優解）。遞迴屬於程式設計領域，其含義是程式呼叫自身。
遞迴的含義是程式呼叫自身的程式設計技巧，是一種實現的方式。遞迴與迭代相對。可以列舉常見的簡單問題，例如計算階乘、計算斐波那契數，都可以通過遞迴或迭代的方式實現。
理論上，所有的遞迴實現都可以使用迭代實現。實現方式和演算法之間沒有絕對的依賴，同一種演算法可能既能用遞迴實現，也能用迭代實現，例如深度優先搜尋，使用遞迴實現是常見的做法，也可以顯性建立乙個棧，使用迭代實現。
動態規劃是一種演算法思想，將原始問題拆分成規模更小且與原始問題性質相同的子問題，利用子問題的解得到原始問題的解。動態規劃的適用條件之一是存在重疊子問題。動態規劃的實現方式可以是自頂向下或自底向上。
使用自頂向下實現時，通常使用遞迴實現，為了充分利用重疊子問題的性質，需要儲存已經計算得到的子問題的答案，這樣下次在遇到相同子問題的時候就可以直接得到答案而不需要重複計算。使用自底向上實現時，通常使用迭代實現，此時可以確保每個子問題只會被計算一次而不會被重複計算。
大多數情況下，動態規劃都是使用自底向上實現的，而另一種演算法則常用自頂向下實現，那就是分治。分治通常使用遞迴實現，也是將原始問題拆分成規模更小且與原始問題性質相同的子問題，利用子問題的解得到原始問題的解。動態規劃和分治的主要區別是重疊子問題的存在以及實現方式。
如果存在重疊子問題，使用動態規劃可以有效降低時間複雜度和空間複雜度。如果不存在重疊子問題，則可以使用分治。
說明動態規劃和分治的區別的乙個典型的例子是斐波那契數。斐波那契數的定義是，f(0)=0，f(1)=1，當n>1時f(n)=f(n-1)+f(n-2)。對於給定的n，需要計算對應的斐波那契數f(n)。
斐波那契數的問題如果用分治求解，不加任何快取，則時間複雜度和空間複雜度會高達O(2^n)，因此分治顯然不是合適的做法。由於存在重複子問題，動態規劃是更合適的做法，時間複雜度和空間複雜度都可以降低到O(n)，如果使用自底向上的做法，還可以使用空間優化，將空間複雜度降低到O(1)。
回到問題，動態規劃是演算法思想，可以有多種實現方式，遞迴是使用自頂向下實現的常用的方式，使用遞迴的方法解動態規劃問題時，為了充分利用重疊子問題的性質，需要儲存已經計算得到的子問題的答案。
5樓：magic2728
動態規劃是一種解決問題的演算法思想，是把問題轉化成更複雜，但是能夠寫出狀態轉移方程的問題，進而可以用遞迴或者遞推的方式來解決。
而遞迴本身僅僅是呼叫自身的一種特殊函式罷了。
6樓：
從思路上來說，動態規劃 < 遞迴。
動態規劃意味著尋找或構造 1. 最優子結構 2. 重疊子問題。
最優子結構一定能用遞迴表示。
遞迴不在乎子問題是否重疊，比如分治。
7樓：
動態規劃（DP 即 Dynamic Programming）指的是題型，即解題思路；而遞迴（Recursion）指的是解題方法，即實現細節。
動態規劃類題型一般有兩種實現方式：
bottom-up 即 table-fill（這個我不知道怎麼翻譯）
top-down 即遞迴（recursion）
至於具體的不同可以看補充材料[1]。
下面是這兩種方式的詳細舉例。
function
fib(n)
return
arr[n];
}時間複雜度：O(n)
空間複雜度：O(n)
這種實現方法的好處在於用空間換時間。時間優化了成了 O(n)，但空間也變成了 O(n)。所以一般一維的 DP 大概會用變數來寫。
function
fib(n)
return
result;}
時間複雜度：O(n)
空間複雜度：O(1)
這樣一來空間複雜度瞬間降低了乙個級別，變為常數級別 O(1)。「利潤」非常可觀。二維及以上的 DP 則會用滾動陣列（rolling array）來優化。
這裡就不舉例了，大家自行搜尋就能看到很多例子。
function
fib(n)
else
}這種實現方法的優勢在於對於每一步看得非常明白，大家能夠輕而易舉地了解什麼是斐波那契數列，對於理解這個結構非常有幫助。但不好的地方在於時間複雜度非常低，低到令人髮指、實際應用中不可接受的地步。
Upper bound time complexity:
Tight upper bound time complexity:
具體推算比較枯燥，可以看這裡[2]。
時間複雜度：
空間複雜度：O(1)
如果你面試的時候僅僅只能寫出這種實現，那基本上這一輩子也與大廠無緣了。
一種常見的優化手段就是上記憶化快取 （Memoization）。
function
fib(n,
memo
)elseif(
ninmemo
)else
return
memo[n
];}console
.log
(fib(8
,{}));
時間複雜度：O(n)
空間複雜度：O(n)
這裡由於有了 memo 不用重複運算，基本上只會跑 n 次，所以時間複雜度為 O(n)，空間複雜度為 O(n)。
所以一般的動態規劃問題考察中，大家會直接上最優解即 bottom-up 的 table-fill，並且用變數或者滾動陣列來優化空間。但值得注意的是最優解並不意味著是最容易理解的實現方式。一般 recurision + memo（業界也叫 DFS + memo）被稱為是萬金油式的 DP，沒有它解不了的題目。
而且時間複雜度和空間複雜度都有很好的平衡。
程式設計規劃
8樓：Forward Star
動態規劃和遞迴都是轉化為子問題去求解，某些動態規劃題應該是可以用遞迴求解的，但由於動態規劃能夠記錄下某個狀態的解，可以避免遞迴的重複計算。
其實動態規劃嚴格來說不算一種演算法吧，就是一種思想，所以它顯得很靈活，沒有固定的模板，在我初學時我就覺得它很像遞推，也很像遞迴。
9樓：啦啦啦啦
動態規劃涉及用已解決的子問題去解決其它子問題。而遞迴也是計算乙個問題用它的結果去計算其他問題。所以遇到可以用遞迴來做的問題就想用遞迴來做是很正常的，個人偏好或者思考習慣，我們都更愛用遞迴來嘗試走出第一步。
但不是非遞迴不可，遞迴跟迴圈在好多地方都可以互換，遞迴只是我們嘗試去解題的一種工具。動態規劃會更專注於『優化』，比如我們要避免重複計算已解決的子問題，遞迴並不能避免我們重複計算子問題。我們不能滿足於用遞迴做出來就完事兒了，應該在此基礎上思考如何利用已解決的子問題去解決其它子問題，那時候你可能會發現有些問題不用遞迴會更快，或者遞迴上還能做進一步優化。
總之我還是鼓勵題主在解題的一開始，可以用遞迴嘗試去解題，但是一定要多思考遞迴的解法之後，是不是能在某些方面做得更好更優。
對動態規劃感興趣的也可以看看我這幾篇文章：
啦啦啦啦：揹包問題詳解
啦啦啦啦：關於揹包問題的一點發散
啦啦啦啦：位元組跳動的一道動態規劃面試題
10樓：Jude Gao
首先動態規劃會重複利用在子問題上的解
並且遞迴是乙個在程式設計實現上的概念即在函式主體的定義中呼叫該函式本身遞迴在演算法的層面上沒有任何意義
而動態規劃是乙個在演算法層面的概念在程式實現上有多種體現方式
DFS 動態規劃 回溯法 遞迴之間的關係是什麼？
青石向晚 回溯是一種思路，DFS 使用了這種思路。遞迴是一種程式設計方式，DFS一般會使用這種程式設計方式。動態規劃也是一種思路，適用於在具備最優子結構的問題中來優化窮舉。跟上面三者沒有什麼特別的關係，勉強算的話自上而下的動態規劃會用到遞迴的程式設計方式。 Jerron 現有的幾個答案都不對啊。遞迴...
動態規劃和貪心的本質區別是什麼？
CRIMX 兩者相似的地方在於技巧性地設計子問題。動態規劃希望復用子問題的解，最好被反覆依賴。其本質還是窮舉，所以當前並不知道哪個子問題的解會構成最終最優解。但知道這個子問題可能會被反覆計算，所以把結果快取起來。整個過程是樹狀的搜尋過程。貪心希望每次都能排除一堆子問題。它不需要復用子問題的解，當前最...
請問動態規劃和滑動視窗的區別是什麼？
Johngo學長 emmm.貌似完全不同 可能有些問題用到了動態規劃解決，但同時利用了滑動視窗的方法。下面是之前寫過的兩篇，可以嘗試看下 Johngo學長 學妹上岸位元組的 動態規劃 寶典Johngo學長 完虐演算法系列 字串 滑動視窗 覆盤總結很清晰的兩篇文章，應該可以幫助你完全解決你迷茫的地方。...