1樓：
錯了。動態規劃的本質是遞推。
遞推可以寫成搜尋的形式，搜尋在程式中的實現體現為遞迴。
然而寫成搜尋的形式後會導致複雜度崩潰，於是加上記憶化使之與樸素遞推複雜度相同。
2樓：「已登出」
遞迴+記憶化確實是解決部分動態規劃問題的有效手段。
但是，需要明白一點，不是每一種動態規劃都可以很方便的用上述方法實現的。
動態規劃的本質應該是在高維的決策空間中按照其拓撲序進行迭代然後求得最優解的演算法。
而遞迴+記憶化很大程度上只是為了避免一些重複的計算。
再者，遞迴演算法還需考慮棧空間的問題。
綜上，動態規劃的本質不是遞迴+記憶化。
3樓：傑瑞
還有樹形dp，更多奇形怪狀的動態規劃，你所說的就是用個vis陣列記錄乙個fun(x)的結果，省的多次計算，實際上這種的dp和線段樹有啥區別嗎，勉強稱之為dp。
這樣說吧，讓你求乙個陣列的最小值，你遍歷一遍，遍歷到下標i的時候，是不是拿到得是當前最優解，也勉強稱之為dp
4樓：黨小陽
我覺得大概可以這麼理解吧。
動態規劃問題的特點就是有最優子結構性質，然後最小的子問題解會一直復用。
所以最優子結構就用遞迴做咯（不過遞迴的問題一般可能會有不用遞迴的快速解法），最小問題的解就記憶下來復用咯。
不過動態規劃是一種問題型別，遞迴是一類解題方法，這麼說其實感覺不是特別對味。
5樓：sin1080
其實是可以這麼理解的，ADM的作者Skiena教授就是這麼講解DP的，因為但凡DP，一定有遞推關係，否則遞推關係都沒有就更別說什麼子問題重複計算了。刷表法的那個陣列d，實際上就是預計算的狀態函式，方框裡的下標就是狀態函式的引數，遞迴加memory和預計算刷表只是實現上的兩種技巧，其本質是一樣的，遞迴加memory更接近本質，刷表則是一種優化。
整個流程說白了就是
先想遞迴發現重複計算通過記憶化等方法弄掉重複計算最後看下能不能通過利用計算順序來做到去掉遞迴用「刷表」方式直接順序計算，能搞定最好搞不定拉倒
實際上我按照這套mindset來考慮dp問題之後，會發現對於並不熟悉的dp題目，明顯構思起來要比直接考慮「有什麼狀態？怎麼擴充套件狀態」這套順手，因為遞迴是很自然的一種思維方式。當然，已經比較熟練直接就能看出來狀態和轉移方程的題目，以及一些狀態實在太顯眼比考慮遞迴還簡單的題目，就不需要用這套了。
PS：有一些優化，使用記憶化搜尋方式實現DP做不了，有的題目會被這個卡死，比如必須用滾動陣列等方式壓縮狀態否則MLE的那種。有一些優化，使用刷表法做不了，比如實際訪問的狀態很稀疏又不能整齊控制順序，你一建表就MLE或者TLE那種。
所以兩種DP主流實現方式都要掌握。
人活著是不是本質就是競爭，突然覺得政治就是真相？
沈雅涵 條件不好，有的盆子生鏽了，飯上面沾滿鐵鏽，至少三分之一的飯是不能吃的，好在生鏽的盆子不多 具體體會到競爭是輪到我領飯的時候 飯在桌上，乙個班六盆飯 六個人按順序自取 乙個人一盆 我發覺乙個鐵盆是生鏽的，但仍然排隊，當然，我盤算了一下，我不是最後乙個，不會取到那個生鏽的 想不到的是，排在我後面...
法律的本質是不是利己？
回聲 一切為了人類文明社會秩序所存在的制度，對於個體來說都是 利己 的。當然也包含法律。法律由國家制定，由國家強制力保證實施的，保障人民權利，監督人民履行義務。 了不起的羅蘋漢 法律的價值包含公正，效益，秩序，自由，人權等等，這些事物毫無疑問在社會層面上都是利 社會 的。馬克思主義說法律是為了維護統...
推理的本質是不是窮舉？
我覺得推理的本質是將未知的狀態或者關係，通過建立模型，帶入模型，補齊模型 什麼是關係？我覺得是在時間尺度上事物之間的作用與影響 影響是間接的，作用是直接的 影響看字意，影子和迴響，其實就是間接的通過其他的開判斷本體。我想了半天那麼直接的用什麼詞，想了想用了作用。如果有更好的詞可以和我說 作用影響的表...