在有些時候，可以「聰明地」實作 DP 來節省記憶體、甚至能獲得常數較小的程式碼。若用直觀的概念解釋的話，就是「適當的丟棄那些再也用不到的狀態」。我們不妨複習一下，DP 本身的意義就是把「算過的東西存起來」，進而用記憶換取時間。同時我們也說過，DP 的能夠加速的理由就在於我們會有「重複子問題」，也就是我們存下來記憶是會被反覆呼叫的，這才能達成加速的效果。
因此，滾動 DP 的主要概念就是再試圖把那些不再有用、不再會被呼叫的狀態都從記憶中移除，如此一來就能有效的省下大量的記憶體空間。
有 $N$ 個物品編號 $1 \sim N$，第 $i$ 個物品的重量和價值分別是 $w_i$ 和 $v_i$。學姐打算從這 $N$ 個物品選其中一些帶走，但她只有大小為 $W$ 的背包，也就是說她選擇的物品總重不能超過 $W$。請問背包能容納的物品的總價值最大是多少？
在背包問題中，所謂的 DP 轉移式是長這樣的：
$$
dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w_i] + v_i)
$$
這時候，一般的寫法肯定是先算完第一排（$dp[1][j]$）、再去算第二排（$dp[2][j]$）、……、一路算到第 $N$ 排。
而眼尖的讀者可能馬上就能發現了：在算完第 $i$ 排之後，$i-1$ 排的資訊就不再有用了！
基於這樣的想法，我們可以用以下兩種方式來實作：
由於每次都只需要兩排的記憶體就好，因此我們把原本會開到 dp[MAXN][MAXW] 的陣列開成 dp[2][MAXW]，並用 0/1 來互換運算過程，如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int MAXW = 100005;
const long long INF = MAXN * 1000000000ll;
long long dp[2][MAXW];
int w[MAXN], v[MAXN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, wmax;
cin >> n >> wmax;
for (int i = 1; i <= n; ++i)
cin >> w[i] >> v[i];
// 初始化
dp[0][0] = 0;
for (int i = 1; i <= wmax; ++i)
dp[0][i] = -INF; // 0 個東西湊不出重量 i > 0
int now = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < w[i]; ++j)
dp[now][j] = dp[!now][j];
for (int j = w[i]; j <= wmax; ++j)
dp[now][j] = max(dp[!now][j], dp[!now][j - w[i]] + v[i]);
now ^= 1;
}
cout << *max_element(dp[!now], dp[!now] + wmax + 1) << "\n";
}這份程式碼跟之前的實作幾乎一樣，就差在與這份程式碼使用了「滾動」的技巧。
因為現在陣列只開了兩排，所以我們在第 24 行宣告一個變數 now，每次要算第 $i$ 排時，now 代表的就是當前這排的值，而 !now 就是 0/1 反轉後 now，所以就代表著前一排。
因此，把原本 i 的部分改成 now、i - 1 的部分 !now，就完成滾動的實作了！
順帶一提，如果「還會有用的排數」不是兩排，而是三排的話，這裡可能就要在 0/1/2 之間做切換，也就不能使用 !now 這種偷吃步的寫法，這部分的細節就交給讀者自行思考了。
滾動 DP 還有一個常見的好寫法：使用 std::vector 來實作。
具體概念是直接把兩排當成兩個 vector 陣列，並在算完一排後直接使用 swap 來交換。而由於 vector 的特性，這裡 26 行的 swap 其實時間複雜度是 $O(1)$ 的！具體理論這裡不好解釋，讀者可以先記下來就好。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 105;
const long long INF = MAXN * 1000000000ll;
int w[MAXN], v[MAXN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, wmax;
cin >> n >> wmax;
for (int i = 1; i <= n; ++i)
cin >> w[i] >> v[i];
// 初始化
vector<long long> cur(wmax + 1, 0), prv(wmax + 1, -INF);
prv[0] = 0;
for (int i = 1; i <= n; ++i) {
cur = prv;
for (int j = w[i]; j <= wmax; ++j)
cur[j] = max(prv[j], prv[j - w[i]] + v[i]);
cur.swap(prv);
}
cout << *max_element(prv.begin(), prv.end()) << "\n";
}看完了上面的程式碼，相信讀者可以感受到更多的簡潔性，包含 19 行的初始化、23 行的賦值等等，這些都是使用 vector 能獲得的寫法優勢。
同樣地，如果「還會有用的排數」不是兩排，而是三排以上的話要怎麼辦呢？其實若使用這個寫法，可能要稍微動點歪腦筋，由於筆者沒有看過什麼比較固定的實作方法，這裡就不做冗餘的解釋，僅給讀者一個可能的實現方法：可以使用 std::rotate 試試看。
要注意，即使上面的題目剛好不會用到，但不論是哪一種寫法，都是在「回收利用」之前用過的記憶體。也因此，剛交換完後所得到的記憶體實際上還是存著更之前的資料。因此，如果寫出 dp[i] = max(dp[i], ...) 這種寫法的話，就有可能不小心拿到舊的資料，這在某些題目可能是會出事的！
而解決方法很理所當然的，就是要記得好好初始化！
實際上，像是費氏數列的這種 DP，很多人會直接用下列的方式來實作：
int fib_dp(int n) {
int a = 0, b = 1;
for (int i = 1; i <= n; ++i) {
int t = (a + b) % MOD;
a = b;
b = t;
}
return a;
}也就是直接紀錄「剛算完的那兩個數字」，以用來推到下一個數字；而算出下一個數字後，就可以把兩項之前的那項丟掉。
沒錯，所謂「丟掉之前的項」就是滾動 DP 的精神，所以上述的寫法其實就是一種滾動 DP！進而達到 $O(1)$ 的記憶體用量。
回頭來看，其實這類寫法幾乎只有在以 bottom up 實作 DP 時才能進行改造，所以這其實也是 bottom up 的優勢所在。
實際上，針對背包問題的滾動 DP，有一個更短的寫法，由於直接解釋起來有點困難，這裡就先上程式碼：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int MAXW = 100005;
const long long INF = MAXN * 1000000000ll;
long long dp[MAXW];
int w[MAXN], v[MAXN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, wmax;
cin >> n >> wmax;
for (int i = 1; i <= n; ++i)
cin >> w[i] >> v[i];
// 初始化
dp[0] = 0;
for (int i = 1; i <= wmax; ++i)
dp[i] = -INF; // 0 個東西湊不出重量 i > 0
for (int i = 1; i <= n; ++i)
for (int j = wmax; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << *max_element(dp, dp + wmax + 1) << "\n";
}讀者可以發現，我們在開 DP 陣列時直接把第一個維度丟棄了，不只如此，在 25 行開始的轉移式也變得非常的簡短，甚至還有些不一樣！
這樣做的原理是什麼呢？讀者可以想像在計算第 $i$ 排的狀態時，$i-1$ 排是如何去更新第 $i$ 排的。
沒錯，這個轉移過程可以想像成：一開始原封不動的複製第 $i-1$ 排，再拿第 $j$ 格去更新 $j+w_i$ 格。
而這時候，如果我們像第 25 行一樣倒過來更新的話——就不會重複更新到了！
什麼是重複更新呢？因為每一個物品只能拿一次，如果 $j$ 更新 $j+w_i$ 後，$j+w_i$ 又去更新 $j+w_i+w_i$，那就會直接錯飛天；但倒過來做的話，$j$ 更新 $j+w_i$ 的時候 $j+w_i$ 早就已經更新後更後面的格子了，也就完美的迴避掉了這個問題。
還沒有完全抓到感覺嗎？我們不妨再來看看另一個例子：
現在有 $N$ 個物品，第 $i$ 個物品的重量為 $w_i$，價值為 $v_i$。每個物品都有無限多個。
你有一個重量限制為 $W$ 的背包，你希望可以在不超過這個背包重量限制的前提下，盡可能塞入價值總和最高的物品。請問你可以塞入最高的物品總價值是多少？
在無限背包的例子中，我們更新第 $i$ 排時也可以想成是先原封不動的複製第 $i-1$ 排，但這次我們不用再倒過來跑了。
為什麼？原本倒過來跑就是想要迴避「重複更新」這個問題，可是無限背包問題的特點就是東西可以重複拿，那不就正合我們意了嗎？
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
const int MAXW = 205;
const long long INF = MAXN * 1000000000ll;
long long dp[MAXW];
int w[MAXN], v[MAXN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, wmax;
cin >> n >> wmax;
for (int i = 1; i <= n; ++i)
cin >> w[i];
for (int i = 1; i <= n; ++i)
cin >> v[i];
// 初始化
dp[0] = 0;
for (int i = 1; i <= wmax; ++i)
dp[i] = -INF; // 0 個東西湊不出重量 i > 0
for (int i = 1; i <= n; ++i)
for (int j = w[i]; j <= wmax; ++j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << *max_element(dp, dp + wmax + 1) << "\n";
}因此，像上述程式碼一樣大膽的寫下去就能輕鬆的寫出正確的程式碼了！
當然，上述的論述並沒有非常的準確，讀者可以多加思考這兩題之間的差別，來好好思考看看這種特殊的滾動 DP 做法最核心的概念為何。
實際上，滾動 DP 除了省下記憶體用量之外，大多數時候滾動 DP 的執行時間其實會比原本的更快！當然，讀者可能會覺得有點怪，畢竟在滾動 DP 的理念中，時間複雜度並沒有改變，只不過是省下記憶體用量而已；我們甚至還多花了一點力氣來處理交換陣列的部分，這樣到底是怎麼讓程式變快的呢？
要知道，電腦是存在快取記憶體這種概念的，這邊就不做太深入的解釋。若用簡單的例子說的話，讀者可以想像自己在處理文書工作，當資料量非常大的時候，處理文書的書桌空間可能有限，所以可能有大多數的資料們都得存放在櫃子內。也就是說，每次要去拿一份不在書桌上的文件時，就得多花一段固定的時間走去櫃子拿資料出來，甚至還得適當的把書桌上的資料放回櫃子內才不會放不下。
不過如果今天資料量夠小，小到書桌空間就放得下的話，狀況就不一樣了——既然我們總是不需要浪費時間在櫃子之間往返，「存取資料」的速度就會快上許多。沒錯，滾動 DP 大多數的常數優化概念便在這裡！
讀者可以想像電腦也有對記憶體做這樣的「分層」，所謂書桌就是存取比較快、但空間相對小的記憶體，而櫃子就是存取比較慢、但空間相對大的記憶體。在沒有使用滾動 DP 的情況下，多出來的資料就得被迫放在櫃子內，消耗多餘的存取時間；而使用了滾動 DP 之後，由於資料量變少，所有的資料都能夠放在書桌上，就可以大大省下存取資料的時間了。
在這個章節中，我們了解到了「滾動 DP」的概念和實作方式，了解到其擁有省空間、甚至有省下時間常數的優勢。同時，我們也發現了在特定狀況下還能夠使用更漂亮的實作方式。
想必讀者讀到這裡，已經學過不少動態規劃方法，可在比賽中才不會有「這題是 DP！」這樣的提示在。因此，在下一個章節中，我們將為大家再做一個總複習，讀者可以針對下列問題先行做一些思考：
針對以下習題，試著學習寫成滾動的形式看看。並試著進一步思考：若寫成功了，你是否有使用到我們上面教過「更短的寫法」呢？你是怎麼辦到的？或如果辦不到的話，為什麼？
有 $N$ 個高棕櫚，經過円円分析後，吃下第 $i$ 個高棕櫚會得到 $A_i$ 的飽足感和 $B_i$ 的滿足感，但円円有一個能承受的飽足感上限 $M$，同時還有吃下的高棕櫚數量上限 $K$，試找出円円在不違反所有限制下能獲得的滿足感最大值。
給定長度為 $n$ 的序列，序列上有一些位置的數字已經給定，試問有多少把剩下位置填入數字的方法，使得序列中任意相鄰兩個數字的差至多為 $1$。
所有填入數字的範圍皆必須介於 $1\sim m$ 之間。
德國放鬆對英國的進攻後，把矛頭指向了東邊——蘇聯。$1943$ 年初，東線的戰鬥進行到白熱化階段。據可靠情報，$90$ 餘萬德國軍隊在庫爾斯克準備發動浩大攻勢。因此，朱可夫元帥要求你立即從遠東的軍工廠運輸大量裝備支援庫爾斯克前線。列車司機告訴你，一趟列車最多可以容納 $V$ 體積的武器裝備，但是你可能不能裝滿，因為列車承受不了那麽大的重量，一趟列車最多可以承載 $G$ 單位的重量。同時，軍工廠倉庫提供給你一份裝備清單，詳細記錄了每件裝備的體積、重量和火力。為了有效支援朱可夫元帥，你要找到一種方案，使得總火力值最大。