有 $N$ 個物品編號 $1 \sim N$，第 $i$ 個物品的重量和價值分別是 $w_i$ 和 $v_i$。學姐打算從這 $N$ 個物品選其中一些帶走，但她只有大小為 $W$ 的背包，也就是說她選擇的物品總重不能超過 $W$。請問背包能容納的物品的總價值最大是多少？
上面的題目敘述，是動態規劃最經典的題型之一——背包問題。
題目敘述簡單易懂，但如果我們貿然的定義 $dp[i]$ 是「前 $i$ 個物品的最大總價值」，會發生什麼事呢？
如果試圖考慮第 $i$ 個物品的選取與否，去試圖從 $dp[i - 1]$ 轉移過來的話，就會發現一個重大的問題：如果只存最佳的價值總和的話，我們無法知道現在拿取第 $i$ 個物品是否會超出限制 $W$！
那如果我們定義 $dp[i]$ 是「前 $i$ 個物品的最佳解」呢？意思就是，$dp[i]$ 至少同時存著「總重量」和「總價值」。這樣會如何呢？
其實還是會錯！考慮以下輸入：
$$
\begin{array}{|c|c|c|c|}
\hline
\text{物品編號} & 1 & 2 & 3\\
\hline
\text{重量} & 1 & 1 & 1 \\
\hline
\text{價值} & 1 & 2 & 3 \\
\hline
\end{array}
$$
如果總重限制是 $W=2$，那麼每個 $dp$ 值應該的答案為
這時候，對於最佳答案的 $dp[3]$，就會沒辦法從「只有物品 $2$」的狀態轉移過來，造成答案錯誤！
所以該怎麼做呢？答案是——直接把當前重量放在狀態裡！
令 $dp[i][j]$ 是「前 $i$ 個物品中，湊出總重量為 $j$ 的最大總價值」，豁然開朗，整個轉移式的寫法就很直接了：
由於重量的資訊被紀錄在狀態上，因此「是否超出重量限制」的判斷就變得非常簡單了。當然，最後別忘記答案必須要是 $dp[N][0\sim W]$ 中的最大值，因為很有可能最佳解會發生在「故意不讓背包重量恰好是 $W$」的時候。
如此一來，因為我們不需要紀錄總重量超過 $W$ 的狀態答案，因此狀態數量就是 $O(NW)$，而轉移又是 $O(1)$，整體的時間複雜度就是 $O(NW)$，這時看一下範圍，明顯可以通過！
以下提供程式碼給讀者，讀者可以自行思考看看其餘的細節，包含初始狀態、負無限大的定義等：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int MAXW = 100005;
const long long INF = MAXN * 1000000000ll;
long long dp[MAXN][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
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < w[i]; ++j)
dp[i][j] = dp[i - 1][j];
for (int j = w[i]; j <= wmax; ++j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
cout << *max_element(dp[n], dp[n] + wmax + 1) << "\n";
}將「數值」放在狀態裡面，是動態規劃上一個經典又稍微不直觀的技巧，但熟悉了之後相信讀者能很快上手。這類技巧的使用時機，有時候甚至可以從題目範圍限制直接「猜出來」，例如在我們這道例題中，可以很明顯的發現 $NW$ 的上限是 $10^7$，這時候就可以試著朝這方向的時間複雜度去構思演算法，甚至就直接是狀態的大小總和。
當然，這招用範圍猜作法的小技巧不是每次都通用的！
現在地上有 $N$ 條鐵棒，第 $i$ 條的長度為 $l_i$。你的目標是要利用這些鐵棒，焊出一條長度為 $L$ 的長鐵棒，請問有辦法嗎？兩條鐵棒如果長度分別為 $a$ 和 $b$，那它們兩個焊起來之後就會變成一條長度為 $a + b$ 的鐵棒，而且這些鐵棒可以任意焊接。
此外，你必須要回答出 $T$ 種這個問題。
像這樣「若干個整數能不能湊出指定整數」的問題，其實也是一種背包問題的簡化版。只是因為現在沒有「最大價值」，所以 $dp[i][j]$ 的定義其實就變成「前 $i$ 條鐵棒能不能湊出長度為 $j$ 的鐵棒」。至於其餘細節就交給讀者自行揣摩了。
有 $N$ 個高棕櫚，經過円円分析後，吃下第 $i$ 個高棕櫚會得到 $A_i$ 的飽足感和 $B_i$ 的滿足感，但円円有一個能承受的飽足感上限 $M$，試找出円円在飽足感不超過 $M$ 時能獲得的滿足感最大值。
不就是一般的背包問題嗎？但先別急著開始寫，看一下範圍，$O(NM)$ 是不是好像不太對勁？
僅管 $NM$ 只有 $10^8$，背包問題的程式碼常數也小，看起來好像能通過，但可別忘了有至多 $10$ 筆測資，如果 $10$ 筆測資都放 $NM=10^8$，這樣很有可能是會超時的！
一般而言，背包問題其實是不存在所謂「跟數值沒關係」的多項式時間演算法的，因此我們一定可以在範圍限制中找到一些蛛絲馬跡讓我們設計出足夠快的演算法。
實際上，有沒有一個「跟數值沒關係」的多項式時間演算法能解決背包問題仍然是一個未解之謎，許多這類的問題通常被世人認為「非常困難」，因而得名「NP 完全」問題。而我們所設計的 $O(NM)$ 演算法，由於把數值大小放在了時間複雜度內，又被稱為「偽多項式時間」，至於為什麼有一個「偽」呢？讀者可以想像在現實世界中，每個物品的價值有可能根本不是整數，而是小數點後可能會有很多位的浮點數，這可以當成 $M$ 其實非常的大，進一步造成問題，可是實際上輸入的大小並沒有變太多！
有關於「NP 完全」和「偽多項式時間」，在未來的章節會有更詳細的解說。讀者在這裡可以先有個基礎的認識就好。若知道哪些問題是「困難」的，其實就可以在理解題目時，快速找到「與原問題不相同」的地方，這些相異之處很可能就會是解題的關鍵！
仔細一看，發現作為「價值」的 $B_i$ 特別地小，只有 $100$ 而已！我們不妨把歪腦筋動到價值身上，來設計出一個跟價值有關的狀態，具體如下：
沒錯，我們換個方向設計狀態，而這也確實能寫出轉移式：
只是現在從「最大價值」變成了「最小重量」而已。不過最終的答案當然不是 $dp[N][i]$ 的最小值，由於我們所求依然是「被飽足感上限 $M$ 限制下的最大滿足感」，也因此，我們應該要找到「最大的滿足感」使得「湊出該滿足感的最小飽足感不超過 $M$」，而這就變成了找到最大的 $i$ 使得 $dp[N][i]\leq M$ 了。
那麼時間複雜度呢？重點是狀態數量，而注意到最大的總滿足感也不過就是 $\sum^{N}_{i=1}{B_i}$，頂多 $10^4$ 而已，乘上 $N$ 再乘上 $T$ 後，也就只有 $10^7$，那肯定能穩定通過這題。
這種「將答案數值放進狀態內」的技巧雖然相對不那麼常見，但也是值得一學的小技巧。同時也想告訴讀者，動態規劃的最終答案並不總是都存在「陣列」內，而是有可能是「表示狀態用的參數」。
這題的實作細節與前面的背包問題非常的相似，就不特別寫出來，讓讀者自行改寫。
有 $N$ 個高棕櫚，經過円円分析後，吃下第 $i$ 個高棕櫚會得到 $A_i$ 的飽足感和 $B_i$ 的滿足感，但円円有一個能承受的飽足感上限 $M$，同時還有吃下的高棕櫚數量上限 $K$，試找出円円在不違反所有限制下能獲得的滿足感最大值。
如果又多了一個「拿取物品的數量上限」，這時候該怎麼辦呢？
可別忘記增加狀態的精髓為何：能夠更準確的維護構造答案的過程。
也因此，在「拿取物品」的過程中，我們會多在意一個參數是「我們拿了幾個物品」，也就能自然的把「目前的物品數量」放進狀態內，得到一個三維的 DP。
一樣，這裡就交給讀者自行改寫了。
現在有 $N$ 個物品，第 $i$ 個物品的重量為 $w_i$，價值為 $v_i$。每個物品都有無限多個。
你有一個重量限制為 $W$ 的背包，你希望可以在不超過這個背包重量限制的前提下，盡可能塞入價值總和最高的物品。請問你可以塞入最高的物品總價值是多少？
與一般的背包問題不同，現在每一種物品有無限多個，這樣會有什麼差別呢？
我們一樣考慮看看原本的狀態定義，$dp[i][j]$ 是「前 $i$ 個物品中，湊出總重量為 $j$ 的最大總價值」，會發現這個狀態定義似乎在無限背包問題還是可行，那關鍵差別就一定是在轉移身上了。
有一個直觀的想法是這樣的：既然我們想知道「第 $i$ 個物品」的轉移過程，那我們可以乾脆去窮舉「第 $i$ 個物品拿了幾個」，也因此可以寫出
$$
dp[i][j] = \max\{dp[i - 1][j], dp[i - 1][j - w_i] + v_i, dp[i - 1][j - 2\cdot w_i] + 2\cdot v_i, \ldots\}
$$
這種轉移式。並且，由於 $j$ 是有限的整數，所以只要窮舉到 $j - k\cdot w_i$ 小於 $0$ 的瞬間就可以停下來了。
不過，這樣的時間複雜度在轉移上就硬生生了多了一個量級，不是很舒服，有沒有比較簡短的轉移方法呢？
事實上，我們可以想得乾淨一些：不要想成我們是一口氣把 $dp[i][1\sim W]$ 一口氣算出來，而是專心的把單一的 $dp[i][j]$ 算出來！
這時候，你在拿取第 $i$ 個物品轉移到 $dp[i][j]$ 時，概念就可以是
而因為「無限」的設定，所以我們當然就不再在乎第 $i$ 個物品有沒有拿過，才會能夠從 $dp[i][j-w_i]$ 這種同一排的狀態轉移過來。
因此，再整理一遍式子後我們可以得出：
$$
dp[i][j] = \max\{dp[i - 1][j], dp[i][j - w_i] + v_i\}
$$
這邊可以注意到我們直接省略先前有提到過的了 $dp[i - 1][j - w_i]$，這是因為該狀態的最佳解也會被 $dp[i][j - w_i]$ 這個狀態考慮到，就不用再重複考慮一次了。
因此，整體時間複雜度就還是 $O(NW)$：$O(NW)$ 個狀態、乘上 $O(1)$ 的轉移時間。
其實，在無限背包的設定中，我們也可以直接考慮 $dp[i]$ 是重量總和為 $i$ 的最大價值總和，進而得到
$$
dp[i] = \max_{w_j\leq i}\{dp[i - w_j] + v_j\}
$$
一樣，因為物品可以重複拿，所以自然就不用在乎「拿取物品的順序」這種資訊來保證每個物品只拿一次了——讀者可以想想看這個狀態定義不適用於一般背包問題的理由來感受到他們的差別。
這樣的方向會帶來 $O(W)$ 的狀態數、$O(N)$ 的轉移時間，時間複雜度也同樣是 $O(NW)$。
在這個章節中，我們以「背包問題」作為主軸，認識了不同感覺的狀態設計方法，知道「數值」本身也是可以被放在狀態上的參數。甚至放在參數的數字不只是題目給的限制，也可以是所求的答案。
不過若讀者嘗試在網路上針對背包問題做搜尋的話，可以找到若干種不同看起來很厲害的寫法，似乎看上去還只用了一個維度當狀態！？還請先別擔心，在下一個章節，我們就會來介紹一下這個厲害的 DP 實作技巧——滾動 DP。
小峰在玩電車遊戲，這個遊戲規則相當簡單。玩家一共要移動 $N$ 次，每次抽出一個數字 $a_i$，小峰可以選擇往左走或往上走 $a_i$ 公尺，小峰需要最小化遊戲結束時所在位置與起點的距離，請問這個最短距離為何？
王老先生有一個置物櫃，共有 $M$ 個相同大小的格子，置物櫃目前已經租給 $n$ 個客戶，第 $i$ 位客戶所租的大小為 $f(i)$ 個格子（$1 \le i \le n$）。目前的承租量總和不超過 $M$，但是現在王老先生自己需要使用 $S$ 個格子的置物櫃，如果剩下的容量不夠，就必須退掉某些客戶的租約。假設每個客戶所租容量只能全退或全不退，而退租第 $i$ 個客戶損失的利益與其所租容量 $f(i)$ 相同，請寫一支程式計算王老先生最小的損失利益，如果不須退租，則損失為 $0$。
給定 $n$ 種硬幣面額 $c_1, c_2, \ldots, c_n$，試求湊出指定總和 $x$ 需要最少幾枚硬幣？
給定 $n$ 種硬幣面額 $c_1, c_2, \ldots, c_n$，試求有幾種用硬幣湊出指定總和 $x$ 的方法？
兩種方法不一樣的定義為「使用硬幣的順序不同即不同」。
給定 $n$ 種硬幣面額 $c_1, c_2, \ldots, c_n$，試求有幾種用硬幣湊出指定總和 $x$ 的方法？
兩種方法不一樣的定義為「使用硬幣的集合不同即不同」。
有 $N$ 個小孩要分 $K$ 顆糖果，其中第 $i$ 個小孩收到的糖果數必須介於 $0\sim a_i$ 之間。若所有的糖果都必須要分完，試求有幾種分糖果的方法？
一開始船上有 $c$ 個種類的水果，第 $i$ 種類有 $n_i$ 顆。現在依序經過 $c$ 個城市，每經過一個城市 $i$ 可以決定要不要把船上所有前 $i$ 種類的水果給當地盤商賣，其中
問若積載成本和銷售成本總和不超過 $T$ 的前提下，最多能賣幾顆水果？