讓我們來看看一道跟先前都不一樣的題目：
今天，臺大程式解題社的其中 $N$ 位選手面向你站成了一個橫排，由左至右的編號為 $1\sim N$，身為這次活動負責人的你，被社長指派必須挑出一些人站出來進行機智問答，這些站出來的人只會往你的方向前進一步，並不會左右移動。不過，邪惡的社長為了增添你的麻煩，特別告訴你說你選出來參加問答的人選必須要滿足以下條件：
你已經知道有幾種挑人的方法，因此調查了一遍每個人的問答能力值，分別為 $a_1, a_2, \ldots, a_N$，代表若第 $i$ 個人被挑選出來參加機智問答，他可以讓總能力值增加 $a_i$，注意到有些人的能力值是負的，代表你挑選他出來參加機智問答反而會讓總能力值變小（可能是因為他身體不舒服吧！）。
現在你的目標是要最大化挑選出來的人的總能力值，請問這個最大值會是多少呢？
讀者可以注意到，這次我們要解的問題已經不再是方法數，而是「最大值」了！相信讀者已經在先前見識過不少這種找到「最佳解」的題目，而理所當然的，在動態規劃的世界中，這種「最佳化問題」的佔比也不小。
同時，伴隨著問題形式的改變，我們的輸入也不再只是單純的一個參數，而是一整串序列！
不過別慌，問題形式雖然變了，解法其實並沒有什麼變。在原本數方法數的問題中，我們是令 $f(n)$ 為 $n$ 個人的答案；而在最佳化的問題中，我們只要想成 $f(n)$ 是「前 $n$ 個人的答案」就好了！
遞迴式大同小異，這裡就直接先寫出來：
$$
f(n) =
\begin{cases}
a_1 & n=1 \\
a_1 + a_2 & n=2\\
\max(f(n - 1), f(n - 2)) + a_n & \text{otherwise}
\end{cases}
$$
可以發現，在解決前 $n$ 個人的答案時，我們同樣是在窮舉站在第 $n$ 個人左邊的是誰，並得到一個子問題，只要已知每個子問題的答案的最大值，再補上第 $n$ 個人，我們就可以在考慮到所有狀況後得到整個問題的最大值！
這邊就先不附上程式碼，供讀者自行練習。
讀者可以發現在前面的問題中，$f(n)$ 已經不再單純的是 $n$ 個人的答案，而是「前」$n$ 個人的答案。這是因為單單一個數字 $n$ 已經不夠描述該問題的全貌，就好比今天我們說 $f(5)$ 是 $5$ 個人的答案，這樣究竟是哪 $5$ 個人呢？
因此，在設計動態規劃演算法的時候我們必須知道，我們在定義要解決的函數時是可以使用「一句話」來描述的。而在競賽程式中，為了溝通方便，我們會開始使用與「函數」、「遞迴式」這類名詞較為不一樣的用語，就讓我們來透過這些常用的用語來帶讀者認識如何在競賽程式中「敘述」一個動態規劃演算法。
在動態規劃演算法中，會有三個重要的元素
就拿我們前面學過的例子來重新用上面的用語講過一遍：
在爬樓梯問題中，一步一步經過若干個階層爬上來的，每當他停在特定的第 $i$ 階，我們就把這個關鍵的停留過程當成一種「狀態」。
而要如何停留在第 $i$ 階呢？一定是從第 $i-1$ 階的狀態或第 $i-2$ 階的狀態轉變過來，兩種轉變方法都給予了停留在第 $i$ 階的可能性。因而產生了轉移式：
$$
dp[i] =
\begin{cases}
0 & i = 0\text{（初始狀態）} \\
1 & i = 1 \\
dp[i - 1] + dp[i - 2] & \text{otherwise}
\end{cases}
$$
在別離太遠中，我們可以依序考慮編號 $1$ 的人、編號 $2$ 的人、編號 $3$ 的人、……就可以觀察到每次挑選編號 $i$ 個人時，便產生了一個值得記憶的「過程」，進而讓我們設計出狀態。
而補上初始狀態的「從編號 $1$ 開始」後，也就有了轉移式：
$$
dp[i] =
\begin{cases}
1 & i = 1\text{（初始狀態）} \\
1 & i = 2 \\
dp[i - 1] + dp[i - 2] & \text{otherwise}
\end{cases}
$$
回到了引發我們重新敘述一遍動態規劃的罪魁禍首，這時候我們再來看一遍：
可以發現就和前一個問題幾乎一模一樣，只是我們在意的值從「方法數」變成了「最大總能力值」，其狀態與狀態間的影響上也從「加法」變成了「取 $\max$」，才有了轉移式：
$$
dp[i] =
\begin{cases}
a_1 & i = 1\text{（初始狀態）} \\
a_1 + a_2 & i = 2 \\
\max(dp[i - 1], dp[i - 2]) + a_i & \text{otherwise}
\end{cases}
$$
找出狀態和轉移後，往往最簡單計算時間複雜度的方法就是
$$
狀態數 \times 轉移時間
$$
就像前面的三個例子都有 $O(N)$ 個狀態、轉移式的計算都是 $O(1)$，因此總時間複雜度就是 $O(N)\times O(1)=O(N)$。
還記得別離太近嗎？若不特別開一個變數紀錄總和，照著一開始所寫下的轉移式寫成程式的話，就會獲得一個「$O(N)$ 個狀態、轉移 $O(N)$」的演算法，進而讓總時間複雜度是 $O(N)\times O(N)=O(N^2)$。
當然還存在著更複雜的狀況，不過這裡就不再多提了。
空間複雜度通常總是比時間複雜度來得單純，這是因為動態規劃的本質就是「記下每個狀態的答案」，也因此空間上的花費就理所當然的是「狀態數量」啦！
到目前為止，我們講解過動態規劃問題的空間複雜度都是 $O(N)$，未來讀者就能逐漸看到不同的空間複雜度了。
若將稍早我們重新提到的前兩個例子與我們之前使用「函數」講解的方式做比較的話，就會發現我們強調了過程的重要性。這也是使用「狀態」這個詞的一大用意之一。
在動態規劃中，意識到自己設計的動態規劃演算法實際上是在對所有可能的「過程」進行歸納是一件很重要的事情。當然，初學時可能還不太能完全掌握以上概念，筆者這邊推薦讀者可以在試圖設計動態規劃演算法是先試著遵守以下守則解題：
我們會順著這個守則帶大家解決以下幾道例題：
一個超級馬拉松比賽將開始。在遊戲中，選手每天需要跑不同的路徑。假設遊戲全部有 $n$ 條路徑；每個路徑得分可以是不同的。如果一名選手不能在規定時間內完成一條路徑，他該路徑得到 $0$ 分；如果玩家完成了一條路徑在一個規定的時間，他得到該路徑設定的得分；如果玩家完成了一條路徑，用較短的時間，他可以得兩倍分數。
小愛想參加這個比賽，她如果在一條路徑上按正常速度來跑，就只能拿到原始分數，如果他加速跑，就能拿到兩倍分數，不過她就會需要在加速跑完後的下一條路徑上休息而速度變慢得到 $0$ 分，請寫一個程式幫助小愛計算哪些路徑應該加速得到兩倍分數而能獲得最高的總得分。
首先是設計狀態，若天真的令 $dp[i]$ 是「跑完前 $i$ 段路徑的最大得分」那就錯了！
這是因為當我們要寫出轉移式時，會想著第 $i$ 段路徑的結束應該是來自第 $i-1$ 段，但問題就在於我們不知道第 $i-1$ 段是否加速了，進而讓我們不知道對於第 $i$ 段路徑的變化是否要歸零處理。
因此這裡讀者必須意識到，所謂「狀態」內必須包含所有跟「變化」有關的資訊，那要怎麼設計呢？
筆者這邊提供的方式是：令 $dp[i]$ 為「跑完前 $i$ 段路徑，且第 $i$ 段並沒有加速的最大得分」。
為何要這樣設計呢？就讓我們接續後面的步驟。
有了前述定義後，對於 $dp[i]$ 就會有兩種轉移：
這分別對應到什麼呢？假設第 $i$ 段的分數是 $p_i$，寫成式子的話就會是
$$
dp[i] = \max(dp[i - 1] + p_i, dp[i - 2] + 2 \times p_{i - 1})
$$
沒錯！有了「最後一段不能加速」的限制後，對於上述的兩種轉移，我們就不會因為前面的加速發生「加速後還不休息」的狀況了。換句話說，也可以想成我們在轉移時強迫加速後一定要跟著一次休息，才完美避免了這個狀況。
除了 $dp[0]$，也就是什麼都還沒跑，的值是 $0$ 外，其實 $dp[1]$ 應該也最好要被當成一個初始狀態。
為什麼要定義這個值呢？這是因為 $dp[1]$ 如果直接呼叫我們的轉移式就會存取到 $dp[-1]$，是直接超出我們想像的非法值，也因此會直接想讓 $dp[1]$ 在一開始就被定義清楚，也就讓完整的 dp 式變成：
$$
dp[i] = \begin{cases}
0 & i=0\\
p_i & i=1\\
\max(dp[i - 1] + p_i, dp[i - 2] + 2 \times p_{i - 1}) & \text{otherwise}
\end{cases}
$$
當然，有另一種做法就是「令 $dp[-1]$ 為負無限大」。這是什麼意思呢？可以想成是因為 $dp[-1]$ 已經是一個「不應該存在的狀態」，所以如果真的想使用這個狀態，就應該給予「無限大的懲罰」，來讓該次轉移肯定會失敗。寫成 dp 式的話就是：
$$
dp[i] = \begin{cases}
-\infty & i=-1\\
0 & i=0\\
\max(dp[i - 1] + p_i, dp[i - 2] + 2 \times p_{i - 1}) & \text{otherwise}
\end{cases}
$$
既然如此，這個負無限大要多大呢？最好是一個「只要採用了，就一定不會是最佳解」的值來避免這個轉移發生，例如因為最大的分數為 $100$，我們知道得分最大最大也就 $2\times 100\times n$ 而已，所以只要設得比 $-200n$ 還小，那麼一旦把這個值加進答案裡，不管後續的狀態再怎麼轉移，也不可能成為最佳答案了。
實際寫程式時，千萬不要真的寫出 dp[-1] 這種東西，這可是妥妥的 Undefined behavior！詳見實作技巧 / 常見錯誤列表對未定義行為的講解。
具體解決方法通常就是靠一個 if 來進行特判，也可以試著改成
int get_dp(int idx) {
if (idx == -1) return -INF;
return dp[idx];
}這種寫法來透過 get_dp(i) 獲取 dp 值，其中 INF 是一個夠大的常數，可以宣告在全域。
以為答案就是 $dp[n]$ 嗎？別忘了 $dp[n]$ 有著「第 $n$ 條路徑不能加速」的限制，所以我們可能會不小心遺漏這個情況！因此，正確的所求答案其實為 $\max(dp[n-1] + 2 \times p_n, dp[n])$ 才對。
有另一個作法是自行加入額外的「第 $n+1$ 條路徑」，但讓他的得分為 $0$，這樣 $dp[n+1]$ 肯定兩種狀況都可以顧慮到！這裡就交給讀者自行思考了。
由於有 $O(n)$ 個狀態，轉移又是 $O(1)$，總時間複雜度自然就是 $O(n)\times O(1)=O(n)$。
從上面的各種方法中挑選後，寫成程式碼就如下：
#include <iostream>
using namespace std;
const int MAXN = 40;
int p[MAXN + 5], dp[MAXN + 5];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
while (cin >> n && n) {
for (int i = 1; i <= n; ++i)
cin >> p[i];
dp[1] = p[1];
for (int i = 2; i <= n + 1; ++i)
dp[i] = max(dp[i - 1] + p[i], dp[i - 2] + p[i - 1] * 2);
cout << dp[n + 1] << "\n";
}
}約翰家的 $n$ 頭奶牛聚集在一起，排成一列，正在進行一項抗議活動。第 $i$ 頭奶牛的理智度為 $a_i$。
約翰希望奶牛在抗議時保持理性，為此，他打算將所有的奶牛隔離成若干個小組，每個小組內的奶牛的理智度總和都要不小於零。
由於奶牛是按直線排列的，所以一個小組內的奶牛位置必須是連續的。請幫助約翰計算一下，最多分成幾組。或告訴約翰這是不可能的。
不如就令 $dp[i]$ 為「前 $i$ 個數字的最佳解」。
在這類「將序列切成若干段」的題目有一個常見的轉移招數：那就是枚舉最後一段的長相為何。
因此，想像以 $i$ 結尾的最後一段的上一段結尾是 $j$ 的話，就可以寫出轉移式：
$$
dp[i] = \max_{1\leq j<i}\{dp[j] + 1 \mid \text{if }\sum^{i}_{k=j+1}a_k\geq 0\}
$$
也就是窮舉 $j$，並檢查 $j+1\sim i$ 的總和有沒有 $\geq 0$ 就可以嘗試使用 $j$ 轉移了。
不過這裡會有一個疑慮：如果沒有一個合法的 $j$ 時該怎麼辦？
這時候最簡單的做法就是拿出前一個例題有提過的方法：賦予 $dp[i]$ 負無限大！讓「嘗試使用該狀態轉移」的獲得無可挽回的懲罰就可以了。讀者可以想想看這裡的負無限大應該設置成多少，配合待會「找出所求答案」的階段做思考。
很單純的，令 $dp[0]=0$ 可以解決所有事情。
很單純的，$dp[n]$ 就會是答案。
不過要怎麼判斷「無解」呢？直接判斷其為負無限大是不對的！這是因為有可能 $dp[n]$ 是嘗試從別的不合法狀態轉移過來的。
這裡只需要利用「負無限大」真的很小的特性，就可以單純用 $dp[n]$ 的值做判斷了，這裡一樣交給讀者思考看看。
狀態數為 $O(n)$，那轉移呢？
若貿然實作前述的轉移式，就會直接獲得 $O(n^2)$ 的轉移時間，這是因為窮舉 $j$ 需要 $O(n)$、計算總和又需要 $O(n)$。
不過還請別太死的照抄轉移式，別忘了我們之前有教過大家「開個變數儲存總和」的技巧，這裡我們只要「倒著窮舉 $j$」，就可以邊窮舉 $j$ 邊維護到當前為止的和了。
參考實作如下，若上述的解說有想不通的地方的話，也可以來這裡看答案：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int arr[MAXN], dp[MAXN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> arr[i];
for (int i = 1; i <= n; ++i) {
dp[i] = -n; // 初始化成一個使用了便無法挽回的值
int sum = 0;
for (int j = i - 1; j >= 0; --j) { // 倒著計算總和以省去重新計算的時間
sum += arr[j + 1];
if (sum >= 0)
dp[i] = max(dp[i], dp[j] + 1);
}
}
if (dp[n] <= 0) cout << "Impossible\n"; // 正是因為使用了負無限大，答案才會 <= 0
else cout << dp[n] << "\n";
}給定一個長度為 $N$ 序列，序列中的第 $i$ 個數字 $a_i$ 表示一個給定股票在第 $i$ 天的價格。
請設計一個演算法計算出最大利潤。在滿足以下條件的情況下，你可以盡可能地完成數次交易（多次買賣一支股票）:
這裡如果令 $dp[i]$ 為「第 $i$ 天結束的最佳解」又會造成問題了，這次的問題是什麼呢？
非常明顯的，除了需要多等 $1$ 天的限制之外，還有一個大問題就是「不知道現在手上是否有股票」。
因此，這裡的狀態就定義為「第 $i$ 天結束，且手上沒有股票的最佳解」。
既然如此，$dp[i]$ 就會有兩種轉移
寫成轉移式的話就會是
$$
dp[i] = \max(dp[i - 1], \max_{1\leq j<i}\{ a_i - a_j + {\color{red}{dp[j-2]}}\})
$$
注意到為了處理多等 $1$ 天的問題，由於我們在後半部分是嘗試在第 $j$ 天買股票，因此 $j-1$ 天是不能有任何動作的，我們才使用 $dp[j-2]$ 作為轉移來源。
不過，如果繼續跟著步驟走，就會發現到了複雜度的步驟，轉移的所花時間是 $O(N)$，整體時間複雜度算起來就會是 $O(N^2)$，肯定會超時！
這裡就得用到本章節最後一個技巧：整理轉移式。
轉移式可不是寫出來就結束的，仔細看著上面式子的右半部份：
$$
\max_{1\leq j<i}\{ a_i - a_j + dp[j-2]\}
$$
注意到因為這個 $\max$ 函數是在窮舉 $j$，所以我們可以把 $a_i$ 提出來變成
$$
a_i + \max_{1\leq j<i}\{- a_j + dp[j-2]\}
$$
如此一來，右邊的部分就跟 $i$ 完全無關了！
不過這樣有什麼用呢？非常有用！如果看一下 $i+1$ 同樣部份的長相：
$$
a_{i+1} + \max_{1\leq j<i+1}\{- a_j + dp[j-2]\}
$$
就會發現 $\max$ 函數內部的取值會剛好比 $i$ 多一個 $-a_i + dp[i-2]$ 而已，這代表我們可以開一個共同變數維護到當前為止的最大值！
因此，轉移複雜度就在這裡優化成了 $O(1)$，非常漂亮。而具體的細節就交給讀者自己思考看看了。
雖然一樣能令 $dp[0]=0$，但別忘了我們在嘗試買第 $1$ 天的股票時會不小心取到 $dp[-1]$ 的值，不過這時候就不算是不合法取值了，直接一起當成 $0$ 就可以了。
當然，$dp[N]$ 就是我們的所求。
經過先前的努力，時間複雜度成功優化至 $O(N)\times O(1)=O(N)$！
這裡就一樣供讀者參考：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int arr[MAXN], dp[MAXN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> arr[i];
int mx = -2e9;
for (int i = 2; i <= n; ++i) {
int val = -arr[i - 1];
if (i >= 3) val += dp[i - 3];
mx = max(mx, val);
dp[i] = max(arr[i] + mx, dp[i - 1]);
}
cout << dp[n] << "\n";
}有一套守則好像就能解決所有動態規劃問題了嗎？是也不是！在上述的守則當中，每一步都可以衍伸出更複雜的狀況，這使得動態規劃有了獨立成一個大主題的價值。
不過讀者也不必太恐慌，光是單純的跟隨著上面這套守則，再了解過幾個常見的解題套路過後，極大多數的動態規劃題目都能迎刃而解，而這也是我們要率先傳授給讀者的——畢竟藝術總是得先從模仿開始。
因此在接下來的章節中，我們會開始帶大家了解設計動態規劃演算法時各種常見的招數，下一個章節就從最基本的「增加維度」開始講起。
有 $N$ 顆石頭，第 $i$ 顆的高度為 $h_i$。
有一隻青蛙一開始在 $1$ 號石頭，他會持續以下動作直到跳到 $N$ 號石頭：
試求青蛙跳到 $N$ 號石頭的最小總花費。
有 $N$ 顆石頭，第 $i$ 顆的高度為 $h_i$。
有一隻青蛙一開始在 $1$ 號石頭，他會持續以下動作直到跳到 $N$ 號石頭：
試求青蛙跳到 $N$ 號石頭的最小總花費。
有 $N$ 個階梯，Takahashi 現在在第 $0$ 層階梯，他每次可以往上爬 $1$ 或 $2$ 層階梯。
不過，第 $a_1, a_2, \ldots, a_M$ 層階梯都壞了，不可以踩在這些層數上。
請問 Takahashi 有幾種爬到第 $N$ 層階梯的方法？輸出答案模 $10^9+7$。
今天，臺大程式解題社的其中 $N$ 位選手面向你站成了一個橫排，由左至右的編號為 $1\sim N$，身為這次活動負責人的你，被社長指派必須挑出一些人站出來進行機智問答，這些站出來的人只會往你的方向前進一步，並不會左右移動。不過，邪惡的社長為了增添你的麻煩，特別告訴你說你選出來參加問答的人選必須要滿足以下條件：
你已經知道有幾種挑人的方法，因此調查了一遍每個人的問答能力值，分別為 $a_1, a_2, \ldots, a_N$，代表若第 $i$ 個人被挑選出來參加機智問答，他可以讓總能力值增加 $a_i$，注意到有些人的能力值是負的，代表你挑選他出來參加機智問答反而會讓總能力值變小（可能是因為他身體不舒服吧！）。
現在你的目標是要最大化挑選出來的人的總能力值，請問這個最大值會是多少呢？