# 蟲洞問題
首先，嘗試拆了一下給的範例測資
可以觀察出一些規律

大膽假設不會有區間重合的現象，並驗證其猜想

解題思路

看起來很像之前上課時提到的矩陣相乘的動態規劃問題，都是以一個區間(i,j)當作一個子問題

遞迴式可以寫成這樣

其中check()函式定義如下

舉個例子實際推演一下
dark matter=(-1,2,6,3,8) 塞-1進去讓index從1開始計比較方便
d1stance=10

假設DP[i][j]代表從位置i到位置j的子序列的最佳解，底下表格即為DP矩陣
1. 一開始能求的就是那些長度是1的那些子問題(初始化條件)
| i \ j | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- |
| 1 | -2 | - | - | - |
| 2 | x | -2 | - |- |
| 3 | x | x | -2 | - |
| 4 | x | x | x | -2 |

2. 接著將長度為2的子問題全部求出來
例如DP[1][2]算法為

| i \ j | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- |
| 1 | -2 | -2 | - | - |
| 2 | x | -2 | - |- |
| 3 | x | x | -2 | - |
| 4 | x | x | x | -2 |

3. 接著將長度為3的子問題全部求出來
例如DP[1][3]算法為

| i \ j | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- |
| 1 | -2 | -2 | -3 | - |
| 2 | x | -2 | - |- |
| 3 | x | x | -2 | - |
| 4 | x | x | x | -2 |

4. 一直以此類推，直到算出DP[1][4]即為所求