動態規劃入門：從記憶化搜索到動態規劃

在開始對動態規劃的講解之前，我們需要先對記憶化搜索進行回顧：

什么是記憶化搜索？

在搜索過程中，當搜索樹中存在大量重復的節點時，我們可以通過引入一個"備忘錄"（通常是一個數組或哈希表）來優化計算。這個備忘錄會記錄第一次搜索到某個節點時的計算結果。當后續再次遇到相同的節點時，就可以直接從備忘錄中獲取之前存儲的結果，避免了重復計算的開銷。

例如，在計算斐波那契數列時，fib(5) = fib(4) + fib(3)，而fib(4)又需要計算fib(3)+fib(2)。如果不使用記憶化，fib(3)會被重復計算多次。使用記憶化后，每個fib(n)只需計算一次。

遞推改遞歸：
在用記憶化搜索解決斐波那契數列問題時，如果我們觀察備忘錄的填寫過程，會發現它是一個從左到右依次填充的過程。具體來說：

先計算并存儲fib(0)和fib(1)的基礎值
然后根據這兩個值計算fib(2)
接著用fib(1)和fib(2)計算fib(3)
以此類推，每個新值都依賴于前面已計算好的值

這種自底向上的計算方式，實際上就是將遞歸過程改寫成了循環形式的遞推。這種改寫不僅減少了函數調用的開銷，還使得計算過程更加直觀。

什么是動態規劃？

動態規劃(Dynamic Programming)是一種用于解決多階段決策問題的算法思想。它將復雜問題分解為多個相互關聯的子問題（稱為狀態），并通過保存子問題的解來避免重復計算，從而顯著提高算法效率。

動態規劃通常適用于具有以下特征的問題：

最優子結構：問題的最優解包含其子問題的最優解
重疊子問題：不同的決策序列會到達相同的子問題

從上述描述可以看出，動態規劃結合了分治法的思想（將問題分解為子問題）和剪枝的思想（通過存儲結果避免重復計算）。典型的應用場景包括：

最短路徑問題（如Floyd算法）
背包問題
最長公共子序列
編輯距離計算

（在這篇文章中，筆者只講解最基礎的動態規劃，典序應用場景的運用將留到后續更新中）

在遞推形式的動態規劃中，我們常用下面的專有名詞來表述，因此，要學好并利用好動態規劃，我們首先要弄清楚每一題中一下的概念：

狀態表示：指 f 數組（備忘錄）中，每一個格子所代表的含義。其中，這個數組也被稱為dp數組，或者dp表。
狀態轉移方程：指 f 數組中，每一個格子是如何利用其他格子推導出來的。
初始化：在填表之前，根據題目中默認條件或問題的默認初始狀態，將 f 數組中若干格子先填上值。

例題輔助理解：

光講概念我相信很多小伙伴不能很好的理解或是看不懂，接下來，筆者將通過兩個例題來幫助理解。

下樓梯：頑皮的小明發現，下樓梯時每步可以走 1 個臺階、2 個臺階或 3 個臺階。現在一共有 N 個臺階，你能幫小明算算有多少種方案嗎？（洛谷P10250下樓梯）

在沒有特殊限制的情況下，下臺階問題可以轉化為上臺階問題來處理。具體來說，相當于小明每次可選擇上1、2 或 3 級臺階。當我們要到達第 i 級臺階時，可能來自 i - 1、i - 2 或 i - 3 級臺階。基于這一思路，可以自然地推導出對應的狀態轉移方程。具體的算法流程如下所示：
算法原理：

狀態表示：f[i] 表示走到第 i 級臺階有多少種方案
狀態轉移方程：f[i] = f[i - 1] + f[i - 2] + f[i - 3]
初始化：f[1] = 1 …根據題意自行填寫
填表順序：從小到大依次填寫
最終結果：f[n]

代碼實現：

int main()
{cin >> n;f[1] = 1, f[2] = 2, f[3] = 4;for (int i = 4; i <= n; i++)f[i] = f[i - 1] + f[i - 2] + f[i - 3];cout << f[n] << endl;return 0;
}

空間優化：通過采用滾動數組技術循環利用數組，可以有效降低空間復雜度。空間優化：通過采用滾動數組技術循環利用數組，可以有效降低空間復雜度。

int main()
{cin >> n;f[1] = 1, f[2] = 2, f[3] = 4;for (int i = 4; i <= n; i++)f[i % 4] = f[(i - 1) % 4] + f[(i - 2) % 4] + f[(i - 3) % 4];cout << f[n % 4] << endl;return 0;
}

數字三角形：觀察下面的數字金字塔。寫一個程序來查找從最高點到底部任意處結束的路徑，使路徑經過數字的和最大。每一步可以走到左下方的點也可以到達右下方的點（洛谷P1216數字三角形）。

在題目中，要求我們找到一條最大路徑，但在這個問題中，我們不能使用貪心算法（易證，這里不再贅述），此時我們就需要使用動態規劃的方式解決，每一個位置 f[i][j] 都是由位置 f[i-1][j-1] 或 f[i-1][j] 移動到的，因此，我們只需要找到max(f[i - 1][j - 1], f[i - 1][j])再加上 a[i][j] 即可找到從起點到達 f[i][j] 位置的最大路徑。最后，我們只需要遍歷一下 f 數組的最下面一行即可找出最大路徑。
算法原理：

狀態表示：f[i][j]表示從[1，1]走到[i，j]位置時，所有方案下的最大權值
狀態轉移方程： f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]
初始化：將所有格子全部初始化為負無窮
填表順序：僅需保證從上到下即可
最終結果：最后一行的最大值

代碼實現：

int main()
{cin >> n;memset(f, -0x3f, sizeof f);for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> a[i][j];f[1][1] = a[1][1];for (int i = 2; i <= n; i++)for (int j = 1; j <= i; j++)f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];int max = 0;for (int i = 1; i <= n; i++)if (f[n][i] > max)max = f[n][i];cout << max << endl;return 0;
}

空間優化：可以將 f 數組從二維降為一維。由于每次更新時都是從左到右順序處理，且使用過的舊值不會被重復利用，因此可以不斷覆蓋原數組，僅保留一維數組來記錄最終結果。可以將 f 數組從二維降為一維。由于每次更新時都是從左到右順序處理，且使用過的舊值不會被重復利用，因此可以不斷覆蓋原數組，僅保留一維數組來記錄最終結果。

int main()
{cin >> n;memset(f, -0x3f, sizeof f);for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> a[i][j];f[1] = a[1][1];for (int i = 2; i <= n; i++)for (int j = 1; j <= i; j++)f[j] = max(f[j - 1], f[j]) + a[i][j];int max = 0;for (int i = 1; i <= n; i++)if (f[i] > max)max = f[i];cout << max << endl;return 0;
}