到目前為止，我們已經學過許多 DP 的概念了，不過很多時候即使成功寫出了狀態和轉移，還是免不了超時，這時候一種解決方式，就是考慮「加速」你的 DP 計算過程來改善演算法的時間複雜度。
就讓我們來複習在狀態與轉移學過的題目：
給定一個長度為 $N$ 的序列，序列中的第 $i$ 個數字 $a_i$ 表示一個給定股票在第 $i$ 天的價格。
請設計一個演算法計算出最大利潤。在滿足以下條件的情況下，你可以盡可能地完成數次交易（多次買賣一支股票）:
還記得當初我們提到，這題的狀態可以定義為「第 $i$ 天結束，且手上沒有股票的最佳解」，如此一來轉移式就能寫成：
$$
dp[i] = \max(dp[i - 1], \max_{1\leq j<i}\{ a_i - a_j + dp[j-2]\})
$$
透過整理，我們可以得到把右半部份變成
$$
a_i + \max_{1\leq j<i}\{- a_j + dp[j-2]\}
$$
上面這個式子的目的，就是為了讓右邊包含在 $\max$ 裡面的部分跟 $i$ 完全無關。而狀態與轉移的文章中提到，這樣的性質可以讓我們用「開共同變數維護最大值」的方法來讓轉移優化成 $O(1)$——這聽起來有點模糊，能不能定義得更清楚一點呢？
實際上，這個共同變數其實是一個正在滾動的前綴最大值！
講詳細一點，我們其實可以想成是在定義
$$
s[i-1] := \max_{1\leq j<i}\{- a_j + dp[j-2]\}
$$
因而對於所有 $1\leq i \leq N$ 都有
$$
s[i] = \max\{s[i], -a_{i} + dp[i-2]\}
$$
特別地，我們令 $s[0] = 0$。
上面這個陣列 $s$ 其是就是所謂的前綴最大值，與我們在基礎演算法 / 前綴和與差分學到前綴和的概念是相同的。只不過有一個差異，那就是我們維護的是「$-a_i + dp[i-2]$」這坨「改寫過的數值」的前綴最大值。
同時，$s$ 這個陣列也能在 $O(N)$ 的時間內同時跟著 $dp$ 陣列一起被算出來，這讓我們可以重新把 DP 轉移式寫成
$$
dp[i] = \max(dp[i - 1], a_i + s[i - 1])
$$
也就能很直接的看出他擁有 $O(1)$ 的轉移時間了！
回到我們之前提過的「開一個共同變數」的概念，其實也就只是觀察到當在計算 $dp[i]$ 時，$s[i-2]$ 以前的數值都已經不會再用到了，所以只不過就是把 $s$ 唯一的維度用滾動的概念壓掉了而已！
想必讀者已經了解到何謂「利用前綴最大值來把 DP 轉移優化到 $O(1)$」這個概念了，不過我們再多深入想一下他的核心精髓。有辦法優化的關鍵就在於，$dp[i]$ 和 $dp[i-1]$ 需要用到的「轉移來源」是差不多的東西！
更準確地說，所謂的「轉移來源」似乎就是被我們當成一坨動態新增的資料，使得我們在做狀態轉移時，可以很好的處理這些資料來迅速回答出我們要的資訊，而這裡「從 $dp[i-1]$ 需要的來源到 $dp[i]$ 需要的來源變化」，剛好也就只需要 $O(1)$ 的時間就能維護好我們需要的「前綴最大值」這個資訊。當然，前綴最大值換成前綴和也是沒有問題的，相關的題目讀者可以在後面的習題中找到。
有了以上觀念，我們就來看看下面這題。
蛋餅找到了一個場地玩跳格子，這個場地由 $N$ 個格子組成，由左至右分別從第一個格子排成一直線到第 $N$ 個格子，而每個格子上都寫著一個數字。
為了確實的消耗卡路里，蛋餅給自己定了一些跳格子的規則：
這樣一來，蛋餅就會有非常多種跳格子的方法可以選擇，於是他開始好奇，他到底有多少種方法可以從起跳到結束呢？而這裡他將兩種跳格子方法不一樣定義成「跳過的格子編號集合不一樣」。
但由於方法數可能很多，因此蛋餅只好奇方法數除以 $10^9+7$ 的餘數，請你寫一支程式告訴蛋餅這個數字是多少吧！
我們一樣很直覺的先令 $dp[i]$ 為「蛋餅跳到格子 $i$ 的方法數」，那應該可以直接地寫出以下的轉移式：
$$
dp[i] = 1 + \sum^{i-1}_{j=1} dp[j] \cdot \left[|a_i - a_j| \leq 2\right]
$$
上面的轉移式中，前面的 $1$ 代表蛋餅直接從格子 $i$ 起跳，後面的部分則是在枚舉蛋餅從哪個格子 $j$ 跳來格子 $i$。
右邊出現的中括號「$[P]$」在數學上被稱為艾佛森括號，代表若括號裡面的條件 $P$ 滿足，其值便為 $1$，否則為 $0$。
當然，直接實作的時間複雜度就是 $O(N^2)$。可是我們好像又不能利用像上一題的前綴最大值來優化，這要怎麼處理呢？
關鍵在於想清楚我們要什麼資訊。我們可以發現，後面的求和部份其實可以想成在查詢「$a_j$ 為特定值」的 $dp[j]$ 之和，因此如果對於給定的特定值 $x$，我們能快速查詢到這個總和的話，只需要查 $a_i-2, a_i-1, a_i, a_i+1, a_i+2$ 共五個值就能得到所求了。
靈活一點，不如我們就多開一個陣列 $\mathrm{sum}[x]$，維護到當前為止，$a_j=x$ 的 $dp[j]$ 之和，這樣每一次算完 $dp[i]$ 之後，主動去更新 $\mathrm{sum}[a_i]$ 這格儲存的值，就可以在 $O(1)$ 時間內完成更新；而要計算 $dp[i]$ 的值時，也只需要查詢 $\mathrm{sum}$ 陣列上的五個值就可以在 $O(1)$ 時間內得到所求！
既然轉移時間是 $O(1)$，整體的時間也就被優化到 $O(N)$ 了。
從以上兩題中，希望讀者可以感受到「維護額外資訊來優化時間」的觀念。
另一種酷炫的 DP 優化方法可以從這題再經典不過的題目中獲得啟發：
給你長度為 $N$ 的一個正整數序列 $a_1, a_2, \ldots, a_N$，請你求出最長嚴格遞增子序列的長度。
所謂嚴格遞增子序列，是指去掉序列中的某些數字之後，剩下的子序列是嚴格遞增的。
這道題目又簡稱「LIS」，是動態規劃中必學的一道題目。
雖然有一個直覺方法是令 $dp[i]$ 為 $a_i$ 結尾的最長嚴格遞增子序列，但這樣的做法要優化的話會需要一些進階的技巧。這裡我們來引入一個比較不直覺的狀態定義方法。
就好像我們在學背包問題的變形問題一樣，我們把答案放在狀態內，定義為
會想要存尾數最小是因為，我們會在意什麼數字能接在當前答案的後面，既然答案的要求是數字要嚴格遞增，那尾數當然是越小越好，才能讓最多的數字接在後面。
這樣的狀態定義方式看起來很蠢：畢竟光狀態就花上 $O(N^2)$ 了，怎麼想都不可能比一開始的直覺方法還要好吧？
先別急，總之我們先把轉移式寫出來看看：
$$
dp[i][j] = \begin{cases}
dp[i - 1][j] & \text{if }a_i\leq dp[i-1][j-1] \\
\min(dp[i - 1][j], a_i) & \text{if }a_i > dp[i-1][j-1]
\end{cases}
$$
也就是去比較前 $i-1$ 個數字長度 $j-1$ 的序列最小尾數能不能讓 $a_i$ 接在後面來計算對應的值。
假設前 $i-1$ 個數字是 $1, 8, 2, 4, 6$，我們來看看 $dp[i-1][j]$ 從 $j=1\sim 4$ 分別會是什麼樣子：
$$
dp[i - 1] = [1, 2, 4, 6]
$$
如果這時候 $a_i$ 是 $3$ 的話，我們看看這個序列會發生什麼事：
$$
dp[i] = [1, 2, {\color{red}{3}}, 6]
$$
如果是 $4$ 的話：
$$
dp[i] = [1, 2, {\color{red}{4}}, 6]
$$
如果是 $5$ 的話：
$$
dp[i] = [1, 2, 4, {\color{red}{5}}]
$$
如果是 $7$ 的話：
$$
dp[i] = [1, 2, 4, 6, {\color{red}{7}}]
$$
好像有什麼很酷的規律出現了，沒錯，每次都只有一個數字會發生改動。
更有趣的是，這個改動還是有跡可循的：如果來的數字是 $a_i$，那肯定是 $\geq a_i$ 的最小數字會被換掉！
當然，像上面 $a_i=4$ 的例子，就是把一樣大的 $4$ 換掉，其實實際上沒有任何改變，但依然能用相同的方式去解釋。
也就是說，其實我們可以透過以下方式來「模擬」出每次 $a_i$ 進來時把 $dp[i-1]$ 變成 $dp[i]$ 的改動：
而要怎麼快速找到 $\geq a_i$ 的最小數字呢？可別忘記我們學過的強大工具：二分搜！更進一步地，我們還可以用 C++ 內建的 lower_bound 函式來搞定。實作起來大致上會長這樣：
vector<int> dp;
for (int i = 1; i <= n; ++i) {
if (dp.empty() || a[i] > dp.back())
dp.push_back(a[i]);
else
*lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
}
// 注意到我們這裡用 0-base 的 vector 來代替 dp 陣列的模擬上面這段程式執行完畢後，得到的 dp 就是最終的 $dp[N]$ 了，整體時間居然只需要 $O(N\log N)$！
我們明明在之前學過，dp 的時間複雜度應該要是狀態數 $\times$ 轉移時間才對，但這裡突然就冒出了一個 $O(N^2)$ 的狀態，卻只有 $O(N\log N)$ 的總時間，究竟是怎麼回事？
其實 dp 的時間複雜度計算不是這麼死的東西，不過現在這種狀況我們是能解釋的：理由是因為，我們從 $dp[i-1]$ 到 $dp[i]$ 的這一個過程中，我們是在 $O(\log N)$ 的時間內一口氣把 $j=1\sim N$ 的值都算好了。
一算就是算 $N$ 個東西，就好像平行處理一樣，那當然能有非常誇張的優化成果囉。
這樣的狀況還有另一種解釋方式：想像上，我們好像就是在試著對第一個維度做「滾動」，我們發現，這個滾動 dp 的序列從 $i-1$ 變成 $i$ 的過程中，變化量居然很小，也就能讓我們透過微小的修改量，搭配快速的尋找方式（二分搜），就能夠高效的處理好一坨轉移了。
有了前面的觀念，讓我們試著用另一個角度來解前面講解過的「跳格子」這題。
用這樣 $O(N^2)$ 的 dp 狀態設計，你能夠用我們在 LIS 學到的「觀察滾動序列變化」的概念把他優化到 $O(N)$ 嗎？跟原本的做法有什麼差別呢？
在本文章中，我們學到了兩個動態規劃的基本優化方法：
希望讀者可以仔細思考看看這兩個技巧的本質為何、共同性又為何——實際上，儘管這兩個作法的出發點不同，但針對優化的部份我們是可以當成獨立的問題去思考的。我們會在後面的章節再次深入探討這個觀念，讀者可以在現階段先試著用自己的方式去理解，相信有了自己的見解會先有一些收穫。
同樣有一個由 $N$ 個格子組成的場地可以玩跳格子，這次，格子上沒有數字，取而代之的是一個直接的限制：
而這個數字集合 $S$，則是由 $K$ 個互不相交的區間 $[L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]$ 所聯集得到。
求從 $1$ 號格子跳到 $N$ 號格子的方法數 $998244353$ 的餘數。
飛黃是一種生物，活在二維座標平面上。
有隻特別的飛黃一開始在座標 $(0, 0)$ 的位置，而且你知道它只會往右上方移動，也就是移動的時只可以走到 $x$ 座標跟 $y$ 座標都不比原本小的位置。
現在座標平面的第一象限上有 $n$ 個位置有果實，給定這 $n$ 個果實的座標，你想要知道這隻特別的飛黃最多可以吃到幾個果實（它必須移動到果實所在的座標才可以吃到果實）。
你在一棟有 $ n $ 層樓的建築物中（樓層編號當然是 $ 1 $ 到 $ n $ 呀），現在你在樓層 $ a $ ，其中樓層 $ b $ 是研究神秘植物「滋訓枝枒」的研究室，因此你被禁止進入樓層 $ b $ 。
無聊的你想要連續坐 $ k $ 趟電梯。你原本在樓層 $ x $ ，你會挑一個樓層 $ y $ ，搭乘電梯從樓層 $ x $ 到樓層 $ y $ ，這樣稱為搭乘一趟電梯；其中為了避免不小心到達禁止進入的樓層 $ b $ ，你會確保樓層 $ y $ 與樓層 $ x $ 的距離小於樓層 $ b $ 與樓層 $ x $ 的距離，也就是 $ |y - x| < |b - x| $ ；另一方面，樓層 $ y $ 要是跟樓層 $ x $ 是同一層的話，電梯根本不會動，所以也要求 $ y \neq x $ 。懶惰的你是不會想要爬樓梯的，所以第 $ i + 1 $ 趟電梯的起點一定會是第 $ i $ 趟電梯的終點（第 $ 1 $ 趟電梯的起點就是樓層 $ a $ ）。
現在的問題非常單純，就是你想知道有多少種不同方法讓你坐 $ k $ 趟電梯，兩種方法被視為同一種方法當且僅當對於所有的 $ i $ （ $ 0 < i \leq k $ ）都滿足兩個方法在坐完第 $ i $ 趟電梯時所在的樓層一樣。
由於答案可能會非常大，請你輸出方法數除以 $ 1000000007 $ 的餘數即可。
給一個長度 $N$ 的正整數序列 $a_1, a_2, \ldots, a_N$ ，對於每一個數字，你都可以把它變成原本的兩倍、把它從序列中移除或者維持原樣。
你希望操作後的序列會是一個每個數字都不小於 $M$ 的非遞減序列（也可以稱作 非嚴格遞增序列），請問這樣子的序列最長可以達到多長呢？
現在有 $n$ 個任務可以執行，其中第 $i$ 個任務需要從第 $a_i$ 天連續執行到第 $b_i$ 天，執行完成後可以獲得 $p_i$ 塊錢。
請問在你一天只能參與至多一個任務的前提下，你可以賺到最多多少錢？
小智的學校在天空之城，父母親每天開直升機送他上下學，上學途中小智可以一邊抓寶。
學校與小智家之間所有的位置均等劃分成 $N \times N$ 的格子，每個格子以座標 $(x, y)$ 表示，其中 $x$ 代表水平距離，$y$ 代表高度，若小智家的座標設為原點 $(0, 0)$，學校的座標則為 $(N-1, N-1)$。 直升機飛行的路線被設定成每次只能向右或向上推進一格，也就是說，若直升機在 $(x, y)$ 上，下一步只能飛達 $(x+1, y)$ 或 $(x, y+1)$，當然，直升機也不可以飛超過 $0 \le x<N$ 及 $0 \le y < N$ 的範圍。
小智上學的路途上一共有 $N$ 隻寶貝，每隻寶貝可以被補獲的範圍是某特定高度而水平座標在某連續區間的格子。明確的說，對於寶貝 $P(i), 0 \le i < N$，要捕抓到 $P(i)$，小智必須經過下列座標之一：$\{(x, y)| S(i)\leq x\leq T(i), y=i\}$，其中 $0 \le S(i), T(i) <N$。
請寫個程式幫助小智的父母親規劃一條路徑以便在從家裡到學校的路上，小智可以抓到最多的寶貝。