區間動態規劃詳解
區間動態規劃是動態規劃大家族中非常重要的一員。顧名思義，它是一種解決區間問題的方法。
讓我們先看一道例題：
石子合併
有
堆石子排成一排，第 i 堆石子有
顆，每次我們可以選擇相鄰的兩堆石子合併，代價是兩堆石子數目的和，現在我們要一直合併這些石子，使得最後只剩下一堆石子，問總代價最少是多少？
Daimayuan Online Judge
例如，初始我們有 3 堆石子，其中的石子數分別是 1， 2， 3，有兩種合併的方法：
先合併前兩堆，代價是 1 + 2 = 3，合併完以後還剩兩堆石子，其中的石子數分別是 3， 3，再把這兩堆石子合併，代價是 6，總代價是 3 + 6 = 9；
先合併後兩堆，代價是 2 + 3 = 5，合併完以後還剩兩堆石子，其中的石子數分別是 1， 5，再把這兩堆石子合併，代價是 6，總代價是 5 + 6 = 11；
第一種方法代價較小，所以答案等於 9。
那麼怎麼來解決這個問題呢？
遞迴法
首先我們考慮用遞迴法來解決石子合併問題。
由於每次我們合併的都是相鄰兩堆石子，
在合併的過程中每堆石子都是由初始時連續的一段石子合併而來
。現在讓我們考慮整個合併過程的最後一步，我們要把最後的兩堆石子合併成一堆石子。
一定存在一個分界線 x，使得兩堆石子中的一堆是初始第 1 堆到第 x 堆石子合併得到的結果，另一堆是初始第 x + 1 堆到第 n 堆石子合併得到的結果。比如說在例子的第一種方法中，x = 2，即最後一次合併的一堆石子是初始第 1 堆到第 2 堆石子合併得到的結果，另一堆是初始第 3 堆石子（也就是初始第 3 堆到第 3 堆石子合併得到的結果）。
當 x 確定的時候，總代價 = 合併初始第 1 堆到第 x 堆石子的最小代價 + 合併初始第 x + 1 堆到第 n 堆石子的最小代價 + 總石子數。但是我們不知道分界線 x 在哪裡更優，所以我們選擇列舉 x 的位置，並且在所有情況中選擇代價最小的一個，即為最後的答案。
定義 f［i］［j］ 表示合併初始第 i 堆到第 j 堆石子的最小代價。現在問題從計算 f［1］［n］ 變成了計算所有的 f［1］［x］ 和 f［x + 1］［n］。需要考慮的區間變小了，接下來是不是可以遞迴啦？
在遞迴的過程中，假如我們想求出 f［l］［r］，也就是合併初始第 l 到第 r 堆石子的最小代價。為了合併這些石子，也會存在一個分界線 m，使得最後一步合併的兩堆石子中的一堆是初始第 l 堆到第 m 堆石子合併得到的結果，另一堆是初始第 m + 1 堆到第 r 堆石子合併得到的結果。當 m 確定的時候，總代價 = 合併初始第 l 到第 m 堆石子的最小代價 + 合併初始第 m + 1 到第 r 堆石子的最小代價 + 初始第 l 到第 r 堆石子的石子總數。同樣的，我們要列舉分界線 m 的位置，並且從中選出代價最小的方案，有：
![f[l][r] = \min_{l \le m < r}(f[l][m] + f[m+1][r]) + \sum_{i=l}^{r}a_i](https://img.heatask.com/upload/website_attach/EyJY1YWiwGxg2jgeOb4xOZ=fG_B+kaluB9xYHEkd8e4T3keVglCMP8=a7ZoY3Qg+ooI-vu96hGsyK_eSBqXpLajItdoY3at+zhy-vu9KhehTZhvKxv4ajvFr1ZoY4qvWHOyKZs4TgsiVs_OKqESnjvjrPnoY4qvWH=4KZs4Jx4lDvoRqh1Ee5dLa1LAJ8Yhjy7X70rta29sy6nDb1wRpLauHm_rIm.jpeg)
在式子中，有兩個部分可能要解釋一下。m 為什麼是從 l 列舉到 r - 1 呢？初始第 l 到第 r 堆石子的石子總數為什麼加在括號外面，為什麼不用每次列舉 m 的時候都重新算一次？
第二個問題比較簡單，由於初始第 l 到第 r 堆石子的石子總數與 m 無關（無論 m 是幾，這個值都不會變），所以可以把它提出放在外面。
關於第一個問題，我們想象下最後一步的兩個邊界情況。一種情況是最後合併的兩堆石子中，一堆是初始第 l 堆，另一堆是初始第 l + 1 堆到第 r 堆合併得到的結果，這對應了 m = l 的情況；另一種情況是一堆是初始第 l 堆到第 r - 1 堆合併得到的結果，另一堆是初始第 r 堆，這對應了 m = r - 1 的情況。分界線 m 不能超出這兩個邊界情況，所以我們把它從 l 列舉到 r - 1 就可以啦！
於是我們可以繼續愉快的遞迴下去，算出所有的 f［l］［m］ 和 f［m + 1］［r］ 的值，用這些值計算 f［l］［r］！直到 l = r ，也就是隻需要合併一堆石子的狀態，遞迴就停止啦！
讓我們來看看程式碼！
#include
using
namespace
std
；
int
n
，
a
［
501
］，
s
［
501
］；
int
solve
（
int
l
，
int
r
）
{
if
（
l
==
r
）
return
0
；
int
ans
=
1
<<
30
；
for
（
int
m
=
l
；
m
<
r
；
m
++
）
ans
=
min
（
ans
，
solve
（
l
，
m
）
+
solve
（
m
+
1
，
r
））；
return
ans
+
s
［
r
］
-
s
［
l
-
1
］；
}
int
main
（）
{
scanf
（
“%d”
，
&
n
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
scanf
（
“%d”
，
&
a
［
i
］）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
s
［
i
］
=
s
［
i
-
1
］
+
a
［
i
］；
printf
（
“%d
\n
”
，
solve
（
1
，
n
））；
}
solve（l， r） 計算的是合併初始第 l 堆到第 r 堆石子的最小代價。
if
（
l
==
r
）
return
0
；
當 l = r，也就是隻需要合併一堆石子時，不需要花費任何代價，返回 0。
int
ans
=
1
<<
30
；
for
（
int
m
=
l
；
m
<
r
；
m
++
）
ans
=
min
（
ans
，
solve
（
l
，
m
）
+
solve
（
m
+
1
，
r
））；
這段程式碼的作用是列舉分界線 m，找出 f［l］［m］ + f［m + 1］［r］ 的最小值。
return
ans
+
s
［
r
］
-
s
［
l
-
1
］；
合併初始第 l 堆到第 r 堆石子的最小代價
。我們用字首和的思想計算初始第 l 堆到第 r 堆石子中的石子總數。
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
s
［
i
］
=
s
［
i
-
1
］
+
a
［
i
］；
在這裡我們引入 s 陣列，s［i］ 等於編號小於等於 i 的堆中的石子總數（初始第 1 堆到第 i 堆石子的石子總數）。那麼初始第 l 到第 r 堆中有多少石子怎麼用 s 陣列表示呢？是不是就是 s［r］ - s［l - 1］ 呀（初始第 1 堆到第 r 堆石子的石子總數 - 初始第 1 堆到第 l - 1 堆石子的石子總數，剩下的就是初始第 l 到第 r 堆石子的石子總數）！
printf
（
“%d
\n
”
，
solve
（
1
，
n
））；
solve（1， n） 即為最後的答案！
記憶化搜尋
遞迴的解法跑得很慢，n = 500 早就徹底歇菜了，為什麼呢？在遞迴的過程當中，同一個區間 ［l， r］ （指的是合併初始第 l 堆到第 r 堆的情況）會被重複計算很多次。比如說，對於區間 ［3， 4］ 來說，計算區間 ［1， 4］， ［2， 4］， ［3， 5］， ［3， 6］， 。。。。， ［3， n］ 時都需要被算一次，這顯然就太慢了！那怎麼辦呢？每次計算的時候，合併初始第 l 堆到第 r 堆石子的最小代價都是一樣的，於是我們可以用一個數組 f 把算過的情況都記下來，f［l］［r］ 中記錄了合併初始第 l 堆到第 r 堆石子的最小代價。每次遞迴到區間 ［l， r］ 的時候，我們首先判斷一下之前這個情況有沒有出現過。如果這是第一次出現，我們繼續往下遞迴，並用算出來的值更新 f［l］［r］；否則，我們直接返回 f［l］［r］ 的值就可以啦！
#include
using
namespace
std
；
int
n
，
a
［
501
］，
s
［
501
］，
f
［
501
］［
501
］；
int
solve
（
int
l
，
int
r
）
{
if
（
f
［
l
］［
r
］
！=
-
1
）
return
f
［
l
］［
r
］；
if
（
l
==
r
）
return
f
［
l
］［
r
］
=
0
；
int
ans
=
1
<<
30
；
for
（
int
m
=
l
；
m
<
r
；
m
++
）
ans
=
min
（
ans
，
solve
（
l
，
m
）
+
solve
（
m
+
1
，
r
））；
return
f
［
l
］［
r
］
=
ans
+
s
［
r
］
-
s
［
l
-
1
］；
}
int
main
（）
{
scanf
（
“%d”
，
&
n
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
scanf
（
“%d”
，
&
a
［
i
］）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
s
［
i
］
=
s
［
i
-
1
］
+
a
［
i
］；
memset
（
f
，
255
，
sizeof
（
f
））；
printf
（
“%d
\n
”
，
solve
（
1
，
n
））；
}
和剛剛的遞迴解法不一樣的是，我們引入了陣列 f，把算過的情況都記下來。
memset
（
f
，
255
，
sizeof
（
f
））；
初始 f 中所有元素的值都賦值成 -1。如果 f［l］［r］ = -1，表示這個情況沒有被計算過。
if
（
f
［
l
］［
r
］
！=
-
1
）
return
f
［
l
］［
r
］；
在計算 solve（l， r） ，也就是合併初始第 l 堆到第 r 堆石子的情況的過程中，如果這個情況之前被計算過了，則直接返回 f［l］［r］。
if
（
l
==
r
）
return
f
［
l
］［
r
］
=
0
；
int
ans
=
1
<<
30
；
for
（
int
m
=
l
；
m
<
r
；
m
++
）
ans
=
min
（
ans
，
solve
（
l
，
m
）
+
solve
（
m
+
1
，
r
））；
return
f
［
l
］［
r
］
=
ans
+
s
［
r
］
-
s
［
l
-
1
］；
否則，我們只要在 return 之前把算出來的值存入 f［l］［r］ 就好啦！
我們再來分析下這個程式碼的時間複雜度。長度為 n 的序列總共有
個區間（實際是
個），每個區間最多被計算到一次，每次計算時分界線最多有
個，所以總的時間複雜度是
。
這就是傳說中的記憶化搜尋啦！顧名思義，記憶化搜尋指的是我們在搜尋（遞迴）的過程中，把碰到過的情況都記錄下來。再次碰到同一個情況的時候，我們不必從頭再計算一次，取而代之的是我們可以直接從記憶中把結果讀取出來。
記憶化搜尋和動態規劃秉承著相似的邏輯，核心問題都是以子問題的解推出母問題的解。
不一樣的是，在動態規劃中拆分問題的過程是在人的頭腦中進行的，而記憶化搜尋拆分問題是在程式中進行的，它的執行模式是在遞迴的過程中先自上而下把母問題拆分成子問題，一直拆分直到不能繼續拆分為止，然後再自下而上把每個子問題的解一一推匯出來。作為對比，動態規劃的程式裡只有自下而上求解每個子問題的解這一個過程。在實戰當中，記憶化搜尋的思維難度相較動態規劃來說一般更低，在讀者早期對動態規劃還不甚理解的時候，不妨先熟練掌握使用記憶化搜尋的技巧，已經可以解決絕大部分的動態規劃類問題。
動態規劃
讓我們換種思路，用動態規劃的想法來解決這個問題，分析過程是和前面的做法類似的。首先，我們來看看這個題的最優子結構、無後效性、狀態以及轉移。
最優子結構：為了計算合併區間 ［i， j］ 的最小代價，我們需要先計算合併所有滿足
的區間 ［i， k］，［k + 1， j］ 的最小代價；有了後者的值，我們就可以算出前者的值；
無後效性：我們只關心合併區間 ［i， j］ 的最小代價，不關心具體是怎麼合併的；
狀態：用 f［i］［j］ 表示合併區間 ［i， j］ 的最小代價；
轉移：
![f[i][j] = \min_{i \le k < j}(f[i][k] + f[k+1][j]) + \sum_{k=i}^{j}a_k](https://img.heatask.com/upload/website_attach/Iuw42jhFNcyh6U2=K46O4_Wxet2w4R9p6dO400zwb_p-7ai1oWHe4qWSxhZ_VhD-iYUMs8eZsc9zx-i9+NyYejoOqQZ_VRr-rtEMs8eYsiB-iS6A1w6_Drae+VZ_Wcpzx4EAaLpPvnlWr-GAgYDyDroe2VZ_Wcpzx49AaLpXOJmEqLsypQLSpSgSIc1kjjvEqWgC0rLT6Y9zk9qvU4CYejw7dtBxf.jpeg)
，分別對應了分界線 k = i， k = i + 1， 。。。。， k = j - 1 的情況，我們從這 j - i 種情況中選出代價最小的方案，即可以更新 f［i］［j］ 的值；
上回也說了在動態規劃中，在算一個問題的解之前，必須事先計算這個問題的所有子問題的解。這一點在這裡如何保證呢？讓我們思索一下，問題 ［i， j］ 的子問題 ［i， k］ 和 ［k + 1， j］ 有什麼共同點呢？對了，他們的長度是不是都比 ［i， j］ 小！如果我們把區間按長度從小到大的順序排好序進行計算，那麼一個問題的子問題是不是都會先於它被計算到呀？
話不多少，讓我們來看看程式碼！
#include
using
namespace
std
；
int
n
，
a
［
501
］，
s
［
501
］，
f
［
501
］［
501
］；
int
main
（）
{
scanf
（
“%d”
，
&
n
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
scanf
（
“%d”
，
&
a
［
i
］）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
s
［
i
］
=
s
［
i
-
1
］
+
a
［
i
］；
memset
（
f
，
127
，
sizeof
（
f
））；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
f
［
i
］［
i
］
=
0
；
for
（
int
l
=
1
；
l
<
n
；
l
++
）
for
（
int
i
=
1
；
i
<=
n
-
l
；
i
++
）
{
int
j
=
i
+
l
；
for
（
int
k
=
i
；
k
<
j
；
k
++
）
f
［
i
］［
j
］
=
min
（
f
［
i
］［
j
］，
f
［
i
］［
k
］
+
f
［
k
+
1
］［
j
］
+
s
［
j
］
-
s
［
i
-
1
］）；
}
printf
（
“%d
\n
”
，
f
［
1
］［
n
］）；
}
我們具體的實現方法是先算所有長度為 1 的區間，再算所有長度為 2 的區間，。。。，最後算所有長度為 n - 1 的區間。對於同樣長度的區間，誰先算誰後算是不關鍵的（它們中的任意一個不可能成為另一個的子問題）。
memset
（
f
，
127
，
sizeof
（
f
））；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
f
［
i
］［
i
］
=
0
；
一開始我們進行初始化操作。因為最後要求最小代價，我們把所有狀態的值賦成無窮大，之後出現更小的值，把它們替換掉就可以了。接著，對於所有的區間 ［i， i］，只有一堆石子，所以不需要合併，因而不需要付出任何代價，把這些 f［i］［i］ 賦值成 0。
for
（
int
l
=
1
；
l
<
n
；
l
++
）
for
（
int
i
=
1
；
i
<=
n
-
l
；
i
++
）
{
int
j
=
i
+
l
；
接著從小到大列舉當前考慮的區間長度 l 以及考慮的區間的左端點 i，對應的右端點 j 等於 i + l。
for
（
int
k
=
i
；
k
<
j
；
k
++
）
f
［
i
］［
j
］
=
min
（
f
［
i
］［
j
］，
f
［
i
］［
k
］
+
f
［
k
+
1
］［
j
］
+
s
［
j
］
-
s
［
i
-
1
］）；
然後列舉分界線 k 的位置，即可以更新出 f［i］［j］ 的值。
printf
（
“%d
\n
”
，
f
［
1
］［
n
］）；
f［1］［n］ 就是答案！
最後讓我們來分析下這個做法的時間複雜度，我們需要列舉區間長度 l、左端點 i 以及分界線位置 k，每個都是 O（n） 級別的，所以總的時間複雜度是
，和記憶化搜尋是一樣的。
石子合併代表了一類涉及到區間的動態規劃問題，其核心思想是按長度從小到大的順序計算每個區間代表的狀態的值。解決這類問題的一般思路就是按上面所說的依次列舉區間長度 l、左端點 i 以及分界線位置 k，然後進行狀態的更新和轉移。
括號序列
給定一個長度為
的字串 s，字串由 （， ）， ［， ］ 組成，問其中最長的合法子序列有多長？也就是說，我們要找到最大的 m，使得存在
滿足
並且
是一個合法的括號序列。
合法的括號序列的定義是：
空串是一個合法的括號序列
若 A 是一個合法的括號序列，則 （A）， ［A］ 也是合法的括號序列
若 A， B 都是合法的括號序列，則 AB 也是合法的括號序列
Daimayuan Online Judge
例如，當 s = ［（［（］） 時，則答案 m = 4，對應的子序列為 （［］）。
怎麼用區間動態規劃的思路來解決這個問題呢？假如我們想知道考慮區間 ［i， j］（
）時最長合法子序列長什麼樣，有多少種可能情況呢？
的最長合法子序列等於
的最長合法子序列，也就是說最左邊的括號
不在當前的最長合法子序列中，問題變成了考慮區間 ［i + 1， j］ 時的情況；
的最長合法子序列等於
的最長合法子序列，也就是說最右邊的括號
不在當前的最長合法子序列中，問題變成了考慮區間 ［i， j - 1］ 時的情況；
如果
和
匹配（
是左括號，
是右括號，並且它們屬於同一種括號型別），那麼
也是潛在的
的最長合法子序列，其中 A 表示
的最長合法子序列，問題變成了考慮區間 ［i + 1， j - 1］ 時的情況；
存在一個分界線 k，
的最長合法子序列分別是 A， B，那麼 AB 也是潛在的
的最長合法子序列，問題變成了考慮區間 ［i， k］ 和 ［k + 1， j］ 時的情況；
根據這四種情況，我們直接來看狀態和轉移（大家可以自己想想最優子結構和無後效性的問題）。
狀態：用 f［i］［j］ 表示
中最長的合法子序列的長度；
轉移：
f［i］［j］ = max（f［i］［j］， f［i + 1］［j］）
f［i］［j］ = max（f［i］［j］， f［i］［j - 1］）
如果
和
匹配，f［i］［j］ = max（f［i］［j］， f［i + 1］［j - 1］ + 2）
列舉分界線 k，f［i］［j］ = max（f［i］［j］， f［i］［k］ + f［k + 1］［j］）
再仔細想一下，情況 1 和 2 其實是不用考慮的，為什麼呢？考慮情況 4，當 k = i 時，有 f［i］［j］ = max（f［i］［j］， f［i］［i］ + f［i + 1］［j］），其中 f［i］［i］ = 0（長度為 1 的串不可能是一個合法的括號序列），簡化以後是和情況 1 一樣的，
不在當前的最長合法子序列中，相當於區間 ［i， i］ 提供的 A 是一個空串；同理，當 k = j - 1 時，有 f［i］［j］ = max（f［i］［j］， f［i］［j - 1］ + f［j］［j］），其中 f［j］［j］ = 0，簡化以後是和情況 2 一樣的，
不在當前的最長合法子序列中，相當於區間 ［j， j］ 提供的 B 是一個空串。
現在我們只剩下了 2 種情況，讓我們一起來看看程式碼！
#include
using
namespace
std
；
int
n
，
f
［
501
］［
501
］；
char
str
［
511
］；
int
main
（）
{
scanf
（
“%d%s”
，
&
n
，
str
+
1
）；
memset
（
f
，
0
，
sizeof
（
f
））；
for
（
int
l
=
1
；
l
<
n
；
l
++
）
for
（
int
i
=
1
；
i
<=
n
-
l
；
i
++
）
{
int
j
=
i
+
l
；
if
（（
str
［
i
］
==
‘（’
&&
str
［
j
］
==
‘）’
）
||
（
str
［
i
］
==
‘［’
&&
str
［
j
］
==
‘］’
））
f
［
i
］［
j
］
=
f
［
i
+
1
］［
j
-
1
］
+
2
；
for
（
int
k
=
i
；
k
<
j
；
k
++
）
f
［
i
］［
j
］
=
max
（
f
［
i
］［
j
］，
f
［
i
］［
k
］
+
f
［
k
+
1
］［
j
］）；
}
printf
（
“%d
\n
”
，
f
［
1
］［
n
］）；
}
程式的基本框架和石子合併問題是一樣的。
for
（
int
l
=
1
；
l
<
n
；
l
++
）
for
（
int
i
=
1
；
i
<=
n
-
l
；
i
++
）
{
int
j
=
i
+
l
；
我們依舊列舉區間長度 l，左端點 i，算出對應的右端點的位置 j。
if
（（
str
［
i
］
==
‘（’
&&
str
［
j
］
==
‘）’
）
||
（
str
［
i
］
==
‘［’
&&
str
［
j
］
==
‘］’
））
f
［
i
］［
j
］
=
f
［
i
+
1
］［
j
-
1
］
+
2
；
如果
和
匹配，執行 f［i］［j］ = max（f［i］［j］， f［i + 1］［j - 1］ + 2）。
for
（
int
k
=
i
；
k
<
j
；
k
++
）
f
［
i
］［
j
］
=
max
（
f
［
i
］［
j
］，
f
［
i
］［
k
］
+
f
［
k
+
1
］［
j
］）；
列舉分界線 k，［i， k］ 提供 A，［k + 1， j］ 提供 B，有 f［i］［j］=max（f［i］［j］， f［i］［k］+ f［k +1］［j］）。
和石子合併問題一樣，我們枚舉了區間長度 l、左端點 i 以及分界線位置 k，每個都是 O（n） 級別了，所以總的時間複雜度是
。
石子合併 II
有
堆石子圍成一個圈，第 i 堆石子有
顆，每次我們可以選擇相鄰的兩堆石子合併，代價是兩堆石子數目的和，現在我們要一直合併這些石子，使得最後只剩下一堆石子，問總代價最少是多少。
Daimayuan Online Judge
例如，現在有 3 堆石子，其中的石子數按順時針方向分別是 1， 3， 2，有三種合併的方法：
先合併前兩堆，代價是 1 + 3 = 4，合併完以後還剩兩堆石子，其中的石子數分別是 4， 2，再把這兩堆石子合併，代價是 6，總代價是 4 + 6 = 10；
先合併後兩堆，代價是 3 + 2 = 5，合併完以後還剩兩堆石子，其中的石子數分別是 1， 5，再把這兩堆石子合併，代價是 6，總代價是 5 + 6 = 11；
先合併首尾兩堆，代價是 1 + 2 = 3，合併完以後還剩兩堆石子，其中的石子數分別是 3， 3，再把這兩堆石子合併，代價是 6，總代價是 3 + 6 = 9；
第三種方案代價最小，所以答案是 9。
方法一
考慮一開始的圓，圓上有 n 堆石子，在相鄰的石子間連邊，一共有 n 條邊。
每次合併相鄰兩堆石子的時候，有一條邊會消失。
兩堆紅色的石子合併時，連線它們的邊會消失
從開始到結束一共要合併 n - 1 次，有 n - 1 條邊會消失，也就是說最後一定會有一條邊沒有消失！
打綠色標記的邊最後沒有消失
考慮打綠色標記的邊最後沒有消失，我們可以理解成這條邊一開始就不存在，現在只剩下了 n - 1 條邊，問題變成了一條鏈的情況，仔細想想，現在是不是和第一道石子合併問題一模一樣啦！
於是乎，我們有了第一個做法，先用 O（n） 的複雜度列舉最後哪條邊沒有消失，再套用石子合併
的解法解決排成一排的情況，總的時間複雜度為
。
然而當 n = 250 時，
的解法實在太慢了，有沒有快點的做法呢？
做法二
現在我們來構造一個長度為 2n 的序列，它是由兩個 a 陣列接起來得到的。也就是說，對於前 n 個位置中的位置 i，對應了原來的第 i 堆石子，對於後 n 個位置中的位置 i，對應了原來的第 i - n 堆石子。
直接在這個序列上用第一題的方法做區間 dp，會發生什麼呢？
假如消失的是第 n 堆和第 1 堆石子之間的邊，是不是變成了一條 1， 2， 。。。， n 的鏈，最小代價是不是 f［1］［n］？
假如消失的是第 1 堆和第 2 堆石子之間的邊，是不是變成了一條 2，。。。， n， 1 的鏈，相當於現在序列中的第 2 到第 n + 1 個位置，最小代價是不是 f［2］［n + 1］？
假如消失的是第 2 堆和第 3 堆石子之間的邊，是不是變成了一條 3，。。。， n， 1， 2 的鏈，相當於現在序列中的第 3 到第 n + 2 個位置，最小代價是不是 f［3］［n + 2］？
。。。
假如消失的是第 n - 1 堆和第 n 堆石子之間的邊，是不是變成了一條 n， 1， 。。。， n - 1 的鏈，相當於現在序列中的第 n 到第 2n - 1 個位置，最小代價是不是 f［n］［2n - 1］？
我們只要在這 n 種情況中取最小值就可以啦！
#include
using
namespace
std
；
int
n
，
a
［
501
］，
f
［
501
］［
501
］，
s
［
501
］；
int
main
（）
{
scanf
（
“%d”
，
&
n
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
{
scanf
（
“%d”
，
&
a
［
i
］）；
a
［
n
+
i
］
=
a
［
i
］；
}
for
（
int
i
=
1
；
i
<=
2
*
n
；
i
++
）
s
［
i
］
=
s
［
i
-
1
］
+
a
［
i
］；
memset
（
f
，
127
，
sizeof
（
f
））；
for
（
int
i
=
1
；
i
<=
2
*
n
；
i
++
）
f
［
i
］［
i
］
=
0
；
for
（
int
l
=
1
；
l
<
2
*
n
；
l
++
）
for
（
int
i
=
1
；
i
<=
2
*
n
-
l
；
i
++
）
{
int
j
=
i
+
l
；
for
（
int
k
=
i
；
k
<
j
；
k
++
）
f
［
i
］［
j
］
=
min
（
f
［
i
］［
j
］，
f
［
i
］［
k
］
+
f
［
k
+
1
］［
j
］
+
s
［
j
］
-
s
［
i
-
1
］）；
}
int
ans
=
1
<<
30
；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
ans
=
min
（
ans
，
f
［
i
］［
i
+
n
-
1
］）；
printf
（
“%d
\n
”
，
ans
）；
}
我們來看看和第一題相比，程式碼多了點什麼。
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
{
scanf
（
“%d”
，
&
a
［
i
］）；
a
［
n
+
i
］
=
a
［
i
］；
}
在讀入的時候，我們把兩個 a 陣列接了起來。
for
（
int
i
=
1
；
i
<=
2
*
n
；
i
++
）
注意序列中現在有 2n 個元素。
int
ans
=
1
<<
30
；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
ans
=
min
（
ans
，
f
［
i
］［
i
+
n
-
1
］）；
printf
（
“%d
\n
”
，
ans
）；
最後我們列舉鏈的起始位置，在 n 種形如 f［i］［i + n - 1］ 的狀態中尋找最小值。
這種把序列倍增（兩個相同的序列接起來）的思路在解決很多圓上問題的時候非常有用，有興趣的讀者可以繼續研究研究。
