查找總和爲特定值的所有子集。找到總和爲特定值的所有子集。遞歸還是DP？
給定一組數字：{1,3,9,12}和目標值= 12。找到與目標值相加的不同子集。
ANS：[3,9]，[12]。
The problem has been asked here.
明明有解決這種問題的兩種方法。遞歸或DP。 問題：你如何權衡這兩種方法？
我的解決方案：DP比較困難，但消耗的內存較少。在遞歸中，你必須多次遞歸地調用該函數，這引入了頭部功能。但它「相當」容易，但消耗更多的內存。
你們認爲什麼？
通常，沒有任何類型緩存的遞歸可以導致指數複雜度問題的解決方案，這個問題可以用多項式或線性複雜度來解決。這是因爲你多次計算相同的部分問題。 memoization的遞歸或迭代解決方案可以通過使用更多內存來降低複雜性。
這就是說，你需要考慮你的輸入的約束。對於更大的輸入，指數解決方案通常是無用的，所以你沒有太多的選擇。同時，在大多數情況下使用額外內存並不是真正的問題，除非您爲內存非常有限的系統開發某些內容（如嵌入式系統）。總之，在大多數情況下，您會想要爲了算法的複雜性而折衷內存，但是您需要根據具體情況來決定。
我猜DP可以通過遞歸或基於方法（自上而下或自下而上）的迭代實現。 通用遞歸解決方案與DP之間的主要區別在於是否需要使用額外的內存，這將是算法運行時間的折衷。基本上，您通過存儲和引用額外的計算來避免這種情況。
對於這個問題一般遞歸或DP，權衡將是通用的遞歸在DP VS 運行使用內存之間。
要考慮的另一件事情並不是所有的問題都符合DP方法。 所考慮的問題，具有下列性質
上述2個屬性對於DP實現是必需的。否則DP不會給你任何優化。
例如：大多數分而治之方法沒有「重疊子問題」屬性。二進制搜索沒有。
希望它有幫助！
DP實際上會消耗更多內存，但它可以讓您大量減少冗餘（不必要的重複）計算次數。 – ruakh