什麼是區間DP
區間DP是由線性DP擴充而來的，分階段的去劃分和解決問題，狀态與元素的排列順序以及上一次的合并操作有着很大的關系，具有以下特點：
合并：能夠将兩個及以上的部分進行合并操作
特征：能夠将問題化為兩兩合并的問題
求解：求解最優答案，通過枚舉合并點可以把原問題分為兩個部分，合并左右兩個部分的最優解得到的就是整個問題的最優解
狀态轉移方程通常形式
定義\(f(i, j)\)為\(i\)到\(j\)區間上的答案，則
\[f(i, j) = DP\{f(i, k)+f(k+1, j)+cost(i, j)\},i\leq k< j \\
DP代表根據實際所需選取以上集合内元素的最優解\\
\]
經典例題：石子合并
本題幾個key point
破環成鍊
這個可以通過把整個區間複制一遍，比如樣例的<code>[4594]</code>變成<code>[4594][4594]</code>，相當于變成一個鍊了
狀态如何定義
定義\(f[i][j]\)為\([i,j]\)區間上進行合并操作所得到的最大值（最小值）
則在求合并結果最大值時，轉移方程就是\(f[i][j] = max(f[i][j], f[i][k] + f[k+1][j] + prefix[j] -prefix[i-1])\)
其中\(i\leq k < j\)，\(prefix[i]\)表示\(1到i\)的字首和
循環順序
最外層枚舉每次合并的區間長度，因為更長的區間答案一定要依賴于短的區間答案，是以最外層從\(1到n\)枚舉所有的區間長度。
接下來，需要枚舉左起點，從\(1到(2n-1)\)，為什麼不枚舉\(2n\)位置呢？因為這個沒必要，這一點實際上會與\(2n-1\)位置一起更新，
它後面沒有元素了，而合并操作需要至少兩個元素，故不需要額外枚舉\(2n\)。
通過左起點和區間長度，我們很容易計算出右端點的值。
最後，枚舉中間結點，也就是分割點，要求分割點比左起點\(i\)要大的同時，不能超過右端點和\(2n\)。
Code