把區間邊界當作狀態。
主要有兩種轉移方法，一種是基於相近的區間：
dp[l][r] = f(dp[l][r-1], dp[l+1][r])
另一種是像下面這樣：
dp[l][r] = f(dp[l][k], dp[k][r])
先手想最大化分數，後手則想最小化先手的分數。
如果先手選 a[l]，後手會在剩下的區間選能讓先手分數最小的方法，也就是 min(dp[l + 1][r - 1], dp[l + 2][r])
因此轉移式如下:
dp[l][r] = max(a[l] + min(dp[l + 1][r - 1], dp[l + 2][r]),
a[r] + min(dp[l + 1][r - 1], dp[l][r - 2]));
iThome鐵人賽
看影片追技術