---
# System prepended metadata

title: 蟲洞問題

---

# 蟲洞問題
首先，嘗試拆了一下給的範例測資
![](https://i.imgur.com/l3QYoXH.png)
可以觀察出一些規律
![](https://i.imgur.com/skBc2U0.jpg)

大膽假設不會有區間重合的現象，並驗證其猜想
![](https://i.imgur.com/PjEjBCV.png)

解題思路
![](https://i.imgur.com/nU121U0.png)

看起來很像之前上課時提到的矩陣相乘的動態規劃問題，都是以一個區間(i,j)當作一個子問題
![](https://i.imgur.com/KEEUfGs.png)

遞迴式可以寫成這樣
![](https://i.imgur.com/qQ92lro.png)

其中check()函式定義如下
![](https://i.imgur.com/5iFOG7i.png)


舉個例子實際推演一下
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]算法為
    ![](https://i.imgur.com/nUk2Adb.png)
    
    | 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]算法為
    ![](https://i.imgur.com/tTTDDZ8.png)
    
    | 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]即為所求
