為了帶出「必要元素」的概念，我們先來幫大家複習一遍我們目前的所學。
（複習）
在動態規劃演算法中，會有三個重要的元素
（複習）增加維度與不增加維度的明顯差異，以例題「股票买卖 V」為例：
（複習）令 $dp[i][j]$ 是「前 $i$ 個物品中，湊出總重量為 $j$ 的最大總價值」，豁然開朗，整個轉移式的寫法就很直接了：
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]);複習完畢，接下來就讓我們進入主題吧！
動態規劃演算法花樣這麼多，有沒有一個很乾脆的概念整理出個「大方向」呢？
其實很多時候，我們在設計一個動態規劃演算法時，只是在遵守著幾個概念而已，而最常被大家提出來的三個概念，筆者在這裡將他們稱做「三大要素」，並一一介紹之。
這也是我們在最一開始就有提過的，就是因為同一個問題會被重複呼叫很多次，才會有「用記憶換取時間」的意義，就好比以下轉移式：
$$
dp[i] = dp[i - 1] + i
$$
上面這種轉移式，所以我們是把陣列取名成 $dp$ 了，但他卻不太算是一個動態規劃演算法，這是因為每個子問題也就只會被後一個狀態呼叫而已，根本沒有子問題會被重複呼叫。
又好比下列這道例題：
有一個數列 $x_1,x_2,\dots,x_n$，求所有非空區間之中，最大的總和是多少。
在網路上，許多人會將這題解釋成一道動態規劃例題，但他們寫出來的轉移式也許會是這樣的：
$$
dp[i] = \max(dp[i - 1] + a_i, a_i)
$$
也就是令 $dp[i]$ 為結尾在 $i$ 的最大區間和，轉移式看起來很自然，但同樣有「每個子問題只被呼叫一次」的問題，因此說他是動態規劃演算法，就有點不太自然。
甚至還可能有人這樣寫：
$$
dp[i] = \max_{0\leq j<i}\{s[i] - s[j]\}
$$
其中 $s[i]$ 是前綴和陣列，為 $x_1, x_2, \ldots, x_i$ 的和。
這連遞迴都沒有，只不過是在「對每個右界獨立找到最好的左界」而已。甚至進一步來說，每個 $dp[i]$ 之間互相是不影響的，導致我們也不清楚該稱呼他們為「$n$ 個不同問題」還是「$n$ 個子問題」。
而拿最直接的例子，在費氏數列的動態規劃作法中，若不將子問題紀錄下來，重複的呼叫就會讓時間複雜度直接退化到指數量級，這時候使用動態規劃演算法將時間複雜度變成多項式時間，其優勢才能被凸顯出來。
在講解背包問題這道例題時，我們曾嘗試過以下這種狀態定義方法：
當時我們馬上就給出了一個「這樣定義狀態會錯」的反例，透過這個反例，我們也了解到了子問題狀態的設計不能太過草率。
為了將這種正確和錯誤的子問題定義方式做出區別，人們對正確子問題的性質有了一個稱呼：最佳子結構。
什麼概念呢？明確的說：
針對前面講的錯誤背包問題狀態定義，就是一種「沒有最佳子結構」的例子，因為當我們讓每個子問題都紀錄自己的最佳解時，更大的子問題就無法從這些子問題中轉移出自己的最佳解了！
設計狀態時沒有最佳子結構，是一個有時候連高手都會犯的錯誤。讀者在思考問題時，若要從動態規劃的角度下手，不妨可以多思考看看：
如果遇到這種狀況，還請務必多想想是否遺漏了什麼「轉移過程中不可或缺的參數」，當遇到這種情況時，最直接的方法就是直接把這個參數放進狀態。
這是一個隱藏性質，到目前為止，讀者可能還不會注意到他的重要性。舉個例題當例子：
xtq 有一個 $1$ 行，$n+1$ 列的棋盤，從左到右編號為 $0$ 到 $n$。初始時刻，在 $m$ 位置有一顆棋子。
xtq 會在接下來的時間裡隨機操作。具體地說，如果某一秒棋子不位於 $n$，那麽他將有 $prb$ 的機率將棋子向左移動一格，$1-prb$ 的機率向右移動一格；否則，他必然將棋子向左移動一格。
現在 xtq 想問你，期望多少秒之後棋子能夠到達 $0$。
由於跟本章節關係不大，我們先不管範圍和輸出的方式。
這裡我們先直接試著用動態規劃解決看看，就先定義 $dp[i]$ 是棋子位於 $i$ 時，期望到達 $0$ 的秒數吧！那麼就有
$$
dp[i] = \begin{cases}
0 & i = 0\\
prb \cdot dp[i - 1] + (1 - prb) \cdot dp[i + 1] + 1 & 0 < i < n \\
dp[i - 1] + 1 & i = n
\end{cases}
$$
如果你很開心的想把上面這段轉移式寫成程式的話，就會發現一個很嚴重的問題：
從頭到尾好像都只有 $dp[0]$ 的值是直接被確定的啊？
這就麻煩了，原本在解動態規劃問題時，我們總是很直接的「從小算到大」，所有的子問題在計算時，所謂「更小的子問題」已經早有解答了。但現在，這些子問題沒有所謂的「大小關係」，這是因為他們會互相呼叫，導致不存在「良好的計算的順序」。
從上面的問題可以注意到，就算能輕易的寫出動態規劃的轉移式，也得幫這些狀態找到「計算的順序」，而確實是存在著一些不好找計算順序的問題，也因此會造成實作上的麻煩。
但這次舉的例子，是直接找不到一個合理的計算順序，由於不是本節要討論的對象，僅做為提示，在上面舉出的問題是可以直接將 $dp[i]$ 當成函數對待後，透過解方程式的方式解決的，但這就不是動態規劃演算法了！
也因此，這種「存在一個良好計算順序」的性質，就被稱作為「無後效性」，是動態規劃演算法中不可或缺的重要性質。在後續的章節中，這樣的概念我們能幫助讀者透過圖論的知識點來進行加強，這裡讀者可以先對他有一個認知就好。
很可惜，想要找到判斷何時能使用動態規劃的通則，是不太實際的，但似乎又能在網路上聽到不少「這題明顯就 DP 啊」的言論，這些人是如何自信地說出這些話呢？
不用懷疑，這通常都是因為他們「寫的題目多」，知道以該種形式出現的題目多數情況都是用動態規劃解決，才能做出這樣的推論。也就是說，難不成我們就只能靠不斷大量刷題來培養對動態規劃的感覺嗎？
刷題固然重要，但針對動態規劃，還是有一些思考上的技巧的：
在筆者的想像中，初學動態規劃的讀者讀到這裡很有可能還是對動態規劃的理解感到有些模糊，但透過一系列的教學，筆者希望能給讀者埋下一些思考上的習慣，讓讀者配合這些學到的東西進行題目的練習後，能更正確並迅速的掌握到動態規劃的精髓。最好的情況就是在刷題的過程能有所領悟，這樣靠自己想到的東西就會真正屬於自己。因此，在頻繁的練習過程中，也別忘了時常反思！
到目前為止，希望讀者對動態規劃已經有一套足夠有系統的理解了。當然，光靠這些理論也許不足以了解動態規劃的全貌，有許多的疑點都還存在著：
就讓我們將這些問題暫時留給讀者思考，並在未來的章節一一為大家解惑！