例如揹包問題，通常我們使用一個 dp[i][j] 數組記錄子問題的解，依次從小到大求解所有子問題。使用記憶化遞歸也可以完成這類工作（例如定義一個 dp(i,j)函數），這樣做只需求解必要的少數幾個子問題即可得到題目的解，不用求解所有子問題。這看似比傳統的遞推做法還快。那為什麼人們常用遞推而不用記憶化遞歸？

  1. 不同的題目用不同的寫法比較方便；
  2. 記憶化有時候空間複雜度更高。

關於揹包，遞推可以滾動數組優化，遞歸就不行。

首先

這兩種寫法的時間複雜度是一樣的

其次

這兩種寫法都很常用，只是對於許多特定的問題

用遞推會減少代碼長度而且看著更優美

遞歸的寫法

您可以來看看【P3953】逛公園 - 洛谷

遞歸形式相對於遞推形式有以下幾個優點：

  1. 更直觀，一旦寫出狀態轉移方程，遞歸形式就相當於「模擬題」了。
  2. 在某些情況下，遞歸能少訪問一些子問題。
  3. 拓撲序列不明，即很難找到子問題之間的執行先後順序，比如一個亂七八糟的遞歸函數。

其中，1. 存在於所有 dp 題中，但 2. 和 3. 極少出現。

而遞推形式有如下優點：

  1. 省時間省空間。減少子程序的調用，降低時間函數中的常數。
  2. 程序短一些
  3. 提供更廣闊的優化空間。有時可以覆蓋數據，從而大大降低空間複雜度（不只是優化常數）。

題主提到了 01揹包，這可以說是3.的體現。其實圖論中的 floyd 演算法 也是把數據覆蓋減小到 [公式] 的空間複雜度的。

詳細解釋：

因為[公式]的兩個子問題都是[公式]，故只要已知數組[公式]，就能得到數組 [公式]，所以只需保留至多 2 個數組即可，即空間複雜度優化為 [公式] 。

想起 noip2017，我沒想到覆蓋，直接用了遞歸形式，導致 d1t3 只AC了 1 個點，剩下 5 個MLE，還有 4 個 RE

其實我以前也有答過一些動規方面的問題：

遞歸問題是否都可以用動態規劃求解？?

www.zhihu.com圖標有什麼問題是動態規劃解不了的？?

www.zhihu.com圖標

其實都可以，複雜度是一樣的。

具體還是因題目而異，在不同的問題中一般會使用不同的寫法，比如圖上的問題使用記憶化搜索就方便得多。在正常循環遍歷的順序已經滿足要求時遞推便更加方便。

推薦閱讀：
相關文章