**Chapter 6 (III)**
### 2D1D與其他
下一題也是學DP的經典練習題。
---
##### P-6-17. 切棍子
有一台切割棍子的機器，每次將一段棍子會送入此台機器時，我們可以選擇棍子上的切割位置，機器會將此棍子在指定位置切斷，而切割成本是該段棍子的長度。現在有一根長度L的棍子，上面標有 $n$ 個需要切割的位置座標，因為不同的切割順序會影響切割總成本，請計算出最小的切割總成本。
下圖是一個例子，切割點是$[3,5,1,4]$，如果依照$3\rightarrow 5 \rightarrow 1\rightarrow 4$的順序切割，第一次的長度是7，第二次切割時所需切割的棍子長度是$7-4=3$，第三次切割時，成本是$3-0=3$，第四次成本是$2$，總成本是$7+4+3+2=16$，這是本例最小的成本。
(註：本圖例取自LeetCode)
Time limit: 2秒
輸入格式：第一行有兩個正整數 $n$ 與 $L$。第二行有 $n$ 個正整數，依序代表由小到大的切割點座標 $p[1]$ ~ $p[N]$，數字間以空白隔開，座標的標示的方式是以棍子左端為0，而右端為 $L$。$N \le 200$，$L \le 1e6$。
輸出：最小的切割總成本。
範例一輸入：
3 10
2 4 7
範例一輸出：
20
範例二輸入：
4 7
1 3 4 5
範例二輸出：
16
---
從題目給的範例，很可能讓我們猜想每次應該取中點或median來切割，但事實上都是錯的。直接思考DP的做法，定義一段棍子的切割成本最直接的方式就是以左右端點，因為是有給座標的，我們就以所給的座標當作第 $1, 2,…, n$ 點，定義$cost(i,j)$ 是第 $i$ 點到第 $j$ 點之間這段的最低切割成本，為了方便，以座標 $0$ 與 $L$ 當作第 $0$ 與第 $n+1$ 點，所以我們要計算的就是 $cost(0,n+1)$。
對任意 $i<j$，$cost(i,j)$ 就是一個子問題，所以我們有$O(n^2)$ 個子問題，現在要找出遞迴式。對於 $j=i+1$，$cost(i,j)=0$，因為中間沒有要切割的點；否則 $j>i+1$，假設第一刀切在 $k$，我們雖然不知道 $k$ 在哪裡，但是一旦第一刀切在 $k$ 之後，剩下兩段的成本就是$cost(i,k)$ 與 $cost(k,j)$。DP的思維：既然不知道 $k$ 是多少，那就全部都算吧！所以我們可以得到
$$
cost(i,j) = \left\{
\begin{array}{ll}
0 & \text{ if } j=i+1 \\
\min_{i<k<j}\{ cost(i,k)+cost(k,j)\} + p[j]-p[i] & \text{otherwise}
\end{array}
\right.
$$
其中 $p[j]$ 與 $p[i]$ 是兩點的座標。這是個遞迴式嗎？
是的，雖然跟之前看到的有點不一樣，遞迴都是大往小，我們注意等號右邊的座標間格 $(k-i)$ 與 $(j-k)$ 都會小於左邊的 $(j-i)$，所以它是區間由大到小的遞迴，類似二分搜與排序的狀況。所以這一題的計算順序稍嫌麻煩，是一個試試 top-down 的好時機。我們可以看到寫top-down DP有多麼簡單(在你找出遞迴式之後)。
以下是範例程式，基本上直接寫遞迴函式差不多。一開始把輸入座標讀進來，因為我們的子問題是所有$(i,j)$，就準備一個二維陣列 $memo$ 當小抄，有一半用不到不需要太吝嗇，第4行將它們初設為 $-1$，用來代表沒有計算過，而將所有$memo[i][i+1]$設為0，然後就直接呼叫 $cost(0,n+1)$輸出。
在函數 $cost(i,j)$中，一進入時先檢查對應的 $memo[i][j]$ 是否不是負的，若是，表示曾經算過，便直接回傳表格內容。否則我們要進行遞迴呼叫來計算，第8~10行就是根據遞迴式寫的計算各種第一刀 $k$ 的可能，在其中取最小值，計算完畢後加上這一段的長度，並在第12行要回傳前先將他寫入表格 $memo[i][j]$ 中。是不是很簡單？這個程式的複雜度是多少呢？直接看遞迴不容易，看表格就好，有 $O(n^2)$ 個格子，每個格子一個不超過$O(n)$ 的迴圈，所以就是$O(n^3)$。這一題是存在優化的方法，不過這些優化需要依靠一些數學上的性質，不是我們這份教材的範圍。
```python=
# P-6-17 rod-cutting, top-down DP O(n^3)
n,L = [int(x) for x in input().split()]
p = [0]+[int(x) for x in input().split()]+[L]
memo = [[-1]*(n+2) for i in range(n+2)]
# min cost of [i,j]
def cost(i, j):
if memo[i][j] >= 0: return memo[i][j]
mincost = 10**9
for k in range(i+1,j):
mincost = min(mincost, cost(i,k)+cost(k,j))
mincost += p[j]-p[i]
memo[i][j] = mincost
return mincost
#
for i in range(n+1):
memo[i][i+1] = 0 # initial condition
print(cost(0,n+1))
```
如果要寫非遞迴非top-down的寫法要如何寫呢？其實也不是多難，我們剛才提到子問題的大小看 $j-i$，所以非遞迴的順序要依照 $j-i$ 由小到大計算，如果看成一個矩陣，計算的順序是由對角線逐漸往右上角算。底下是非遞迴的範例程式，要小心迴圈的邊界，這個程式裡面是用一個變數代換 $leng=j-i$，這樣比較好思考也比較不容易寫錯。
```python=
# P-6-17 rod-cutting, bottom up DP O(n^3)
n,L = [int(x) for x in input().split()]
p = [0]+[int(x) for x in input().split()]+[L]
cost = [[0]*(n+2) for i in range(n+2)]
# min cost of [i,j]
for leng in range(2,n+2): # leng = j-i
for i in range(n+2-leng): # j<n+2
j = i+leng
cost[i][j] = min(cost[i][k]+cost[k][j] \
for k in range(i+1,j)) + p[j] - p[i]
#
print(cost[0][n+1])
```
下面一題是類似的習題，也是2D1D的DP，這裡同樣只要求$O(n^3)$的複雜度，這一題同樣存在考數學性質的優化。
---
##### Q-6-18. 矩陣乘法鏈
兩個矩陣A與B要相乘，必須滿足A的行數等於B的列數，若A是$p\times q$的矩陣，B是$q\times r$的矩陣，則$A\times B$的結果是一個$p\times r$的矩陣，而需要的純量乘法數假設是$p\times q\times r$。
矩陣乘法滿足結合律，也就是說$A\times B\times C = (A\times B)\times C = A\times (B\times C)$，可是不同順序所需要的純量乘法數不同。
輸入$p[0], p[1], …, p[n]$，代表有 $n$ 個矩陣相乘的乘法鏈，而它們的矩陣的大小依序分別是$p[0]\times p[1]$、$p[1]\times p[2]$、…、 $p[n-1]\times p[n]$，請找出最好的相乘順序使得使用的純量乘法數的總和最少。
舉例來說，$n=3$，矩陣大小為，$A1: 3 \times 5$, $A2: 5 \times 4$, $A3: 4 \times 2$
乘法順序為$(A1 \times A2) \times A3$ 時，乘法數 $3 \times 5 \times 4 + 3 \times 4 \times* 2 = 84$；若乘法順序為$A1 \times (A2 \times A3)$時，乘法數$3 \times 5 \times 2 + 5 \times 4 \times 2 = 70$。最少的純量乘法數為70。
Time limit: 3 秒
輸入格式：第一行是正整數 $n$。第二行有 $n+1$ 個正整數， $p[0]$ ~ $p[n]$，數字間以空白隔開。$n \le 200$，$p[i] \le 200$。
輸出：最小的純量乘法數量。
範例一輸入：
3
3 5 4 2
範例一輸出：
70
範例二輸入：
4
5 1 3 4 2
範例二輸出：
30
---
下一題出現在APCS的考試中，算是歷屆比較難的題目，因為不在常見的套路中。
---
##### P-6-19. 階梯數字 (APCS201802) (@@)
一個正整數如果從高位數往低位數看過去，每一位數字只會相等或變大，則我們稱它為階梯數字，例如：9、234、777、11222233。給定一正整數N，請計算不大於N的階梯數字總共有幾個，請注意本題只算正整數，所以0不算階梯數字，而且階梯數字不會以0開始。
提示：對於$N$不大的情形，例如100000，我們可以枚舉每一個不超過$N$的數字來判斷。對於$N$很大的時候，就需要比較快速的方法了。我們知道所有的一位數1 ~ 9都是階梯數字，如果要計算 $D$ 位數的階梯數字總數，我們可以依據最高位數字分成9類，然後根據$(D - 1)$位的9類階梯數字總數來計算。
Time limit: 3 秒
輸入格式：輸入一個正數字N。$N \le 1e30$。
輸出：不大於N的階梯數字個數。
範例一輸入：
25
範例一輸出：
22
範例二輸入：
101
範例二輸出：
54
範例一說明：1 ~ 9, 11 ~ 19, 22 ~ 25，共22個。
範例二說明：1 ~ 9, 11 ~ 19, 22 ~ 29, 33 ~ 39, 44 ~ 49, 55 ~ 59, 66 ~ 69, 77 ~ 79, 88 ~ 89, 99，一共有54個。
註：本題當年考試時範圍為$N\le 1e18$，但該範圍太小，這裡把它放大到1e30。
---
要判斷一個數字是否是階梯數字並不難，只要把每一位數字拆解出來再檢查是否單調上升就可以了，題目的提示中也提到，數字範圍小的時候可以枚舉，但N很大時就必須想快速的方法了。這一題比較需要思考，我們先來看看如何以枚舉來解簡單的子題。以下是範例程式，我們設計一個副程式 $check(k)$ 用來判斷$k$ 是否是階梯數字，將 $k$ 換成字串後從高位往低位檢查，如果有下降的狀況即回傳False，如果都沒有，最後回傳True。主程式中就把1開始的所有數字都拿來檢查看看。
```python=
# p-6-19 stepping number, slow enumerate and check
def check(k): # check if k is stepping number
s = str(k)
for i in range(1,len(s)):
if s[i]<s[i-1]: return False
return True
#
n = int(input())
total = 0
for i in range(1,n+1):
total += check(i)
#
print(total)
```
上述方法當然只能通過$n$很小的測資，我們再來看一個稍好但還是不夠好的解法。我們寫一個$inext(k)$函數找出$>k$的第一個階梯數。寫法很簡單，將$k+1$轉成字串 $s$，$s[0]$ 不需健查，由 $s[1]$開始，如果比前一個小，從他開始就要換成前1個的值。主程式從1開始，一直找下一個，直到超過$n$為止。這樣的程式$inext$執行的次數跟答案的大小一樣，所以比前一個方法好，但是數字太大時還是不行。
```python=
# p-6-19 stepping number, slow, finding next
def inext(k): # find next stepping number
s = str(k+1)
for i in range(1,len(s)):
if s[i]<s[i-1]:
s = s[:i] + s[i-1]*(len(s)-i)
return int(s)
#
n = int(input())
total = 0
i = 1
while i <= n:
total += 1
i = inext(i)
#
print(total)
```
接著看完全解的方法。看題目的提示：「如果要計算D位數的階梯數字總數，我們可以依據最高位數字分成9類，然後根據$(D - 1)$位的9類階梯數字總數來計算。」舉例來說明，假設 $N = 358$是一個三位數，要計算不大於358有多少階梯數字：
* 我們可以用最高位數分成4類：以0, 1, 2, 或3開頭的三位階梯數，其中0~2開頭的所有階梯數都要包含，但3開頭的只要不大於358的階梯數
* 3開頭不大於358的階梯數，進一步可分成33開頭、34開頭、以及35開頭，其中35開頭的只要不大於358開頭的。
* 33開頭的三位階梯數其實就是3開頭的二位數，同樣的，34開頭的三位數就是4開頭的二位數。
* 35開頭不超過358的就是不大於8的一位數，有4個，355~358。
從提示與上面的例子可以看出所需要的方法分兩大步驟：
* 計算一個表格step[][]，step[i][j]為 j 開頭的 i 位階梯數字的個數。
* 依據輸入的數字N，在表格中挑選所需要累加的表格位子。
以下的表格是4位數以內的step表格。
| | j=0 | j=1 | j=2 | j=3 | j=4 | j=5 | j=6 | j=7 | j=8 | j=9 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| i=1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| i=2 | 9 | 9 | 8 |7| 6| 5| 4| 3| 2| 1|
|i=3| 54| 45| 36| 28| 21| 15| 10| 6| 3| 1|
|i=4| 219| 165| 120| 84| 56| 35| 20| 10| 4 |1|
首先看表格如何計算。表格的第一列對應到 $i=1$ 位數的情形，此時根據定義除了 $j=0$ 是 0(因為0不是階梯數字)之外，其它都是1。再看表格最右方的欄，$j=9$ 代表以 $9$ 開頭的階梯數字，很容易知道不管幾位數，9 開頭的只有一個 $99…9$。對於 8 開頭的 2 位數 $step[2][8]$，它的第1位是 8，第2位就必須不小於 8，所以 $step[2][8] = step[1][8] + step[1][9]$，同理，$step[2][7] = step[1][7] + step[1][8] + step[1][9]$，所以我們可以推論出
$$
step[i][j] = \sum_{k=j}^{9} step[i-1][k]
$$
如果我們進一步把 $step[i][j+1]$ 帶入計算式右方，可得
$step[i][j] = step[i][j+1] + step[i-1][j]$。
也就是說，除了第1列與最後一欄之外，每一個格子都是它的右方與上方格子相加的和。所以我們可以 $i$ 從小到大，$j$ 從 8 到 0，很容易地計算整個需要的表格。
第二個步驟要根據輸入的數字挑選出表格中的數字來相加。以上面舉例的 $N=358$ 來看，上方表格中有標記的是前面所討論應該要加起來的格子，假設輸入 $N$ 的每一位數儲存在$n[\ ]$陣列中而 $leng$ 是$N$的位數，在此例中也就是$n[0]=3$、$n[1]=5$、$n[2]=8$ 而 $leng=3$，計算過程如下：
* 從 $n[0]$ 開始看，因為 $n[0]=3$, $leng=3$，所以要加 0, 1, 2 開頭的三位數，也就是 $step[3][0]+step[3][1]+step[3][2]=135$。
* 現在考慮的是 3 開頭的 3 位數，$n[1]=5$，所以要加入的是 3 與 4 開頭的 2 位數，也就是 $step[2][3]+step[2][4]=13$。
* 最後考慮的是 35 開頭的 3 位數，$n[2]=8$，所以要加的是 5 ~ 8 開頭的 1 位數，也就是$sum(step[1][5:9])=4$。
最後的答案就是 $135+13+4=152$。
以上大致找出了規則，但還有一個問題要處理，上面的例子N本身是個階梯數字，這樣處理沒錯，我們來看看N不是階梯數字時候的情形。例如 $N=353$，前兩位數的推論方式是一樣的，但是看到第3位時，$n[2] = 3 < n[1]$，所以最後的1位數是不要加的。又例如 $N=317$，3位數的推論依舊成立，但看第2位時發現 $n[1] = 1 < n[0]$，所以後面都不要計算了，事實上我們發現第一個往下降的位數時，後面就都不需要算了，就相當於後面都是0是一樣的，例如 $N=3357499$ 的答案跟$N=3357000$ 是一樣的。
根據上面的規則可以寫成以下的範例程式。第4行將每一位數以數字方式放在list 中。第7 ~ 15行根據上面推出的規則計算表格，第18 ~ 22行根據輸入數字加總表格，請注意最後的那個for迴圈的else，如果for迴圈沒有被break，也就是N是階梯數字，則迴圈結束後要補一個進去。
```python=
# p-6-19 stepping number,
# build step table first and then count the number
n = [int(d) for d in input()]
total = 0
# step[i][j] for i-digits and start with j
step = [[1]*10 for i in range(len(n)+1)]
# build step table
step[1][0] = 0 # 0 is not stepping number
# step[i][j] =sum(step[i-1][k] for k>=j)
# or = step[i][j+1] + step[i-1][j], suffix sum
for i in range(2, len(n)+1):
#step[i][9] = 1
for j in range(8,-1,-1):
step[i][j] = step[i][j+1] + step[i-1][j]
#
# counting
total = sum(step[len(n)][:n[0]])
for i in range(1,len(n)):
if n[i] < n[i-1]: break
total += sum(step[len(n)-i][n[i-1]:n[i]])
else: total += 1 # input is a stepping number
print(total)
```
以下這一節最後兩個例題維度已經不是2D，以下我們看一個很有名的交換網路。
---
##### P-6-20. Hyper-cube path
一個維度為 $n$ 的hypercube是由 $2^n$ 個節點組成的網路，每個節點被賦予唯一一個 0 ~ $2^n-1$ 的編號，對於任兩個節點 $i$ 與 $j$，他們之間會有邊相連若且惟若 $i$ 與 $j$ 的**二進位編碼恰好相差一個位元**，我們對於每個節點 $i$ 給予一個正整數的權重 $w(i)$，請找出編號 0 到編號 $2^n-1$ 的一條最短路徑，使得該路徑所經過的點權重總合(包含起點與終點)為最大。
Time limit: 2 秒
輸入格式：第一行是正整數 $n$，第二行則是這 $2^n$ 個節點的正整數權重 $w(0), w(1),…,w(2^n-1)$，數字之間皆以一個空白間隔，其中 $n<18$ 而每個權重值為非負整數不超過100。
輸出：最大權重總和。
範例一輸入：
2
1 2 3 4
範例一輸出：
8
範例二輸入：
3
1 2 3 4 5 6 7 8
範例二輸出：
21
範例一說明：1(00) -> 3(10) -> 4(11)，總和8，括弧內為節點邊號的二進位。
範例二說明：1(000)-> 5(100) -> 7(110) -> 8(111)，總和21。
---
一個點代表一個 $n$-bit的正整數，兩點可以直接相通若且惟若兩個數字只差一個bit，我們知道起點就是$00…0$，終點是$11…1$，每走一步就是將一個 0-bit換成 1，所謂最短路徑就是不會 0-bit 換 1-bit 後又換回 0，所以路徑的走法就是有 $n!$ 種，也就是更換bit的排列順序。不過不是要求路徑數，而是哪一條路徑經過的權重總和最大。其實這一題跟方格單調路徑是類似的，只是圖形比方格棋盤複雜而已。
在方格棋盤時，每一個格子的前置狀態是它的左方與上方格子，在這一題hyper-cube(超立方體)時，一個數字點的前置狀態是他所有為 1 的 bit 換成 0，以 1001101 為例，它的每一個 1-bit換成 0 就是可能走到它的前置狀態，所以一共有四個(如下圖)。
有了這個概念後，我們必須找DP的計算順序，這一題是top-down的好範例，因為計算順序比較麻煩。每一步把一個 0-bit改成 1，所以我們應該沿著 1-bit 個數少的往多的順序來計算，也就是先算一個 1-bit的，然後兩個 1-bit的，…，這實在非常麻煩。
我們來看看top-down有多簡單，以下是範例程式。遞迴函數在第3 ~ 8行，相同的，進來先檢查表格 $memo[goal]$ 是否已經算過$(>0)$，如果算過直接回傳。接著我們跑一個迴圈找所有前置狀態的最大值，對於每一個bit，$(goal\ \&\ (1<<i))$ 檢查 $goal$ 的第 $i$ 個bit是否為1，如果是，以 $(goal$ ^ $(1<<i))$ 把第 $i$ 個bit換成0就是它的一個前置狀態，其中'^'是Exclusive-OR的位元運算這裡就是將$goal$的第 $i$ bit反向。最大值計算完畢後記得加上該點的權重並且寫入表格 $memo$。
```python=
# p-6-20 hypercube path, top-down
# max weight to reach goal
def dp(goal):
if memo[goal] >0: return memo[goal]
# check each bit, find max previous state
memo[goal] = max(dp(goal^(1<<i)) for i in range(n) \
if goal & (1<<i)) + w[goal]
return memo[goal]
#
n = int(input())
w = [int(x) for x in input().split()]
memo = [0]*(1<<n) # 0 for unvisited
memo[0] = w[0]
print(dp((1<<n)-1))
```
這一題沒辦法寫非遞迴的形式嗎？當然是可以，我們需要找出一個計算順序，滿足每一個點的前置狀態都在他之前出現，第一個可能想法是根據1-bit的個數由少到多，但這樣的順序不太容易找。另外一個想法是以我們第7章要講的graph裡面的BFS的順序，我們在範例程式中有放一支這樣的寫法，請有興趣的人自己去看。
事實上這題有個更簡單的bottom up 順序，以下是賴楷宗老師提供的解法：因為每個點的前置狀態都比它少一個 1-bit，也就是說，從二進位代表的數值上去看，**前置狀態都比較小，從小到大計算就可以了**！所以Bottom up的DP可以很簡單的寫出來，以下是範例程式。
```python=
# p-6-20c hypercube path, bottom-up
# from small to large is a topological sort
n = int(input())
w = [int(x) for x in input().split()]
dp = [0]*(1<<n)
dp[0] = w[0]
for v in range(1,(1<<n)):
# find max dp of predecessor
imax = 0
for i in range(n):
if v & (1<<i):
imax = max(imax, dp[v ^ (1<<i)])
dp[v] = w[v] + imax
#
print(dp[-1])
```
其中第 9 ~ 12 行找前置狀態最小值的迴圈可以寫在一個 max() 迴圈中，如果我們把DP值直接寫在 $w$中，我們可以寫得更簡潔，範例程式如下，這個程式不含註解只有五行。但是類似這樣的寫法時請注意，max()函數中不可以是空的，以這題來說，如果$v$從0開始跑將會是錯的，因為0沒有1-bit，max()函數中將是空的。
```python=
# p-6-20c hypercube path, bottom-up
# from small to large is a topological sort
n = int(input())
w = [int(x) for x in input().split()]
for v in range(1,(1<<n)):
# find max dp of predecessor, dp in w
w[v] += max(w[v^(1<<i)] for i in range(n) if v & (1<<i))
#
print(w[-1])
```
下一題也是top-down的好例子。
---
##### P-6-21. 刪除邊界 (APCS201910)
一個矩陣的第一列與最後一列以及第一行與最後一行稱為該矩陣的四條邊界線，如果某一條邊界線的內容都是相同元素，則可以刪除該邊界線。如果一條邊界線的內容不完全相同，你可以修改某些格子的內容讓邊界線的內容變成相同後，再刪除該邊界線。矩陣在刪除一條邊界線後，還是一個矩陣，但列數或行數會減少一，本題的目標是重複執行修改與刪除邊界的動作，最後將整個矩陣刪除。輸入一個0/1矩陣，請計算最少要修改多少個元素才能將整個矩陣刪除。請注意：根據定義，只有一列或是只有一行的矩陣可以不需要任何修改就可以被全部刪除。
Time limit: 2 秒
輸入格式：第一行為兩個不超過25的正整數 $m$ 和 $n$，以下 $m$ 列 $n$ 行是矩陣內容，順序是由上而下，由左至右，矩陣內容為0或1，同一行數字中間以一個空白間隔。
輸出：最少修改次數。
範例一輸入：
4 5
0 1 0 1 1
1 1 1 0 1
0 0 0 0 0
0 0 0 1 0
範例一輸出：
2
範例二輸入：
3 5
0 0 0 1 0
1 0 1 1 1
0 0 0 1 0
範例二輸出：
1
範例一說明：刪除最後一列(修改1成0，成本1)，刪除最後一列(成本0)，刪除最後一列(修改一個1，成本1)，成本總和2。
範例二說明：刪除最右行(修改1個1，成本1)，刪除最右行(成本0)，刪除第一列(成本0)，修改最後一列(成本0)，總和1。
---
給一個矩陣，每次刪除一個邊界，刪除邊界的成本是該邊界線上0與1比較少的個數，要計算最小的刪除總成本，也就是刪除邊界的最好的順序。我們在第一章的Q-1-11曾經看到這一題，當時的要求是以遞廻的方式來解，所以矩陣的大小比較小，遞迴的時間複雜度是$O((m+n)4^{m+n-2})$，因為每次有4個選擇，每選擇一次，$m+n$會減少1。
從DP的想法來看，因為刪除的是邊界，需要計算的不外乎所有可能的子矩陣，也就是某一塊矩形，那麼有多少矩形呢？有$O( mn)$個可能的左上角與$O(mn)$個可能的右下角，所以有$O( m^2n^2)$個，以top-down的寫法，反正稀哩糊塗的拉個四層廻圈把表格建好，然後照遞迴的方式稍微改一下就可以了，因為4維陣列以下是範例程式，雖然程式不很短，但只是四個邊界每邊都要算一次，其實程式碼很簡單。時間複雜度$O((m+n)m^2n^2)$
```python=
# p-6-21a top-down, 4-d array
# (left, top, right, bottom)
tab = [[[[-1]*40 for i in range(40)]
for j in range(40)]for k in range(40)]
def cost(l, t, r, b):
if l==r or t==b: return 0
if tab[l][t][r][b] >=0 : return tab[l][t][r][b]
n1 = sum(a[t][l:r+1]) # cost of top row
mcost = min(n1, r+1-l-n1) + cost(l, t+1, r, b)
n1 = sum(a[b][l:r+1]) # cost of bottom row
c = min(n1, r+1-l-n1) + cost(l, t, r, b-1)
mcost = min(mcost, c)
n1 = 0 # cost of left column
for i in range(t, b+1):
n1 += a[i][l]
c = min(n1, b+1-t-n1) + cost(l+1, t, r, b)
mcost = min(mcost, c)
n1 = 0 # cost of right column
for i in range(t, b+1):
n1 += a[i][r]
c = min(n1, b+1-t-n1) + cost(l, t, r-1, b)
mcost = min(mcost, c)
tab[l][t][r][b] = mcost
return mcost
#end of cost
m, n = map(int, input().split())
a = [[] for x in range(m+1)]
for i in range(m):
a[i]=[int(x) for x in input().split()]
print(cost(0,0,n-1,m-1))
```
四維陣列看起來有點囉嗦，如果會用字典，這題用dict(tuple)蠻合適的，範例程式中有這樣的寫法，請有興趣的讀者自行參考。
那麼非遞迴的寫法呢？要計算的矩形顯然需要從小算到大，精確一點的說，寬度由小到大且高度由小到大，對於每一個寬度與高度，再枚舉所有可能的左上角位置，以下是範例程式，我們將計算一列與一行的成本寫成副程式，這樣程式比較清爽。
```python=
# p-6-21 bottom up
# the cost of boundary line (row,le) to (row,right)
def r_cost(row, le, right):
n1 = sum(a[row][le:right+1]) # number of 1
return min(right-le+1 - n1, n1) # min(n1,n0)
# the cost of boundary line (top,col) to (bot,col)
def c_cost(col, top, bot):
n1 = 0 # num of 1
for i in range(top, bot+1):
n1 += a[i][col]
return min(n1, bot-top+1-n1)
#end of cost
m, n = map(int, input().split())
a = [[] for x in range(m+1)]
for i in range(m):
a[i]=[int(x) for x in input().split()]
dp = [[[[-1]*40 for i in range(40)]
for j in range(40)]for k in range(40)]
for h in range(1,m+1): # height
for w in range(1,n+1): # width
for top in range(m-h+1): # top
for le in range(n-w+1): # left
if w==1 or h==1:
dp[h][w][top][le] = 0
else:
dp[h][w][top][le] = \
min(dp[h-1][w][top+1][le] + r_cost(top,le,le+w-1),
dp[h-1][w][top][le] + r_cost(top+h-1,le,le+w-1),
dp[h][w-1][top][le+1] + c_cost(le,top,top+h-1),
dp[h][w-1][top][le] + c_cost(le+w-1,top,top+h-1))
#
print(dp[m][n][0][0])
```
## 進階題(\*)
DP的題目很多，有些在競賽中出現的往往需要某些特殊資料結構與特別的優化技巧，**這些題目形式對APCS來說是超出範圍的**，以這份教材的原出發點，或許並不適合將他們放進來。不過看這份教材的也許有些是對競賽程式有興趣的，所以選了幾題不太複雜的放在這一節以供參考，如果覺得有些困難，**可以跳過它們**。
下一題是LIS的變形加權版。
---
##### P-6-22. 文無第一武無第二(@@)(*)
在一個群體中有 $n$ 個成員，編號為 1 ~ $n$，第 $i$ 個人的戰力為 $p[i]$，現在想要挑選一些人組成一個團隊擔任特別的任務。目前除了戰力外，還考量兩項能力值：程式力 $c[i]$ 與數學力 $m[i]$。俗話說「文無第一，武無第二」，如果挑選的人員中某一位的程式力與數學力都不如另外一位的話，他就會非常的沮喪而導致團隊總戰力受到傷害。你的目標是要挑出一個戰力總和最大的團隊，而且如果 $i$ 與 $j$ 都是被挑選的人的話，不允許$c[i]<c[j]$且$m[i]<m[j]$。
Time limit: 3 秒
輸入格式：第一行是正整數 $n$。第二行有 $n$ 個正整數，代表戰力 $p[1]$ ~ $p[n]$，第三行有 $n$ 個非負整數，代表程式力 $c[1]$ ~ $c[n]$，第四行有 $n$ 個非負整數，代表數學力 $m[1]$ ~ $m[n]$，同行數字間以空白隔開。$n$ 不超過1e5，戰力總和不超過1e9，個程式力與數學力均不超過1e8。
輸出：最大戰力總和。
範例一輸入：
5
2 4 1 3 7
1 2 3 3 4
6 7 4 5 1
範例一輸出：
15
範例二輸入：
5
1 2 3 4 9
4 5 4 5 8
3 6 4 5 7
範例二輸出：
9
範例一說明：挑選i=2~5，戰力總和4+1+3+7=15。
範例二說明：挑選i=5，戰力總和9。
---
如果我們將每個人的 $c[i]$ 看成X座標，$m[i]$ 看成Y座標，$p[i]$ 看成點的權重，這題就是平面上給 $n$ 個點座標與權重，要找一些點的權重總和最大，條件是不允許某點的XY座標皆大於另外一點。如果我們從左往右看，就是一條左上往右下逐步遞減(非遞增)的序列，如果從右往左看，就是找一個權重最大的LIS (longest increasing subsequence)，只是依照題意，等號是允許的(前面LIS那一題等號是不允許的)。
這一題比基本LIS難的原因主要不在排序，而是權重。在只需要考慮長度時，因為長度必然是1, 2, 3,…，所以我們很容易的將長度 $L$ 的最小可能結尾存在一個陣列 $last[L]$ 中，但在加權版本，我們要存的是以某數 $t$ 結尾的最大權重，而且必須保持資料的單調性(結尾越大，權重越大)。以下的範例程式是用list來存DP值，複雜度是$O(n^2)$。
```python=
# P-6-22 max anti-chain weighted LIS O(n2)
#from sortedcontainers import SortedList
import bisect
n = int(input())
pi = [int(x) for x in input().split()]
ci = [int(x) for x in input().split()]
mi = [int(x) for x in input().split()]
# sort by large c first, breaking tie by small m
seq = sorted((-c,m,p) for c,m,p in zip(ci,mi,pi))
dp = [(-1,0)] #
# (m, P) largest P with ending m, (-1,0) is sentinel
for c,m,p in seq:
i = bisect.bisect_left(dp, (m+1,)) -1 # the last <= m
w = dp[i][1]+p
# remove larger ending but smaller weight
while i+1<len(dp) and dp[i+1][1]<=w:
dp.pop(i+1)
dp.insert(i+1,(m,w)) # same key is ok
#
print(dp[-1][1])
```
這一題要做到 $O(n\log n)$ 需要一個動態的資料結構來維護單調DP序列，Python 有SortedList可以用，但它不在標準函數庫中，以下是範例程式，複雜度是$O(n\log(n))$。
```python=
# P-6-22 max anti-chain weighted LIS O(nlogn)
from sortedcontainers import SortedList
n = int(input())
pi = [int(x) for x in input().split()]
ci = [int(x) for x in input().split()]
mi = [int(x) for x in input().split()]
# sort by large c first, breaking tie by small m
seq = sorted(zip(ci,mi,pi), key=lambda x: (-x[0],x[1]))
dp = SortedList([(-1,0)]) #
# (m, P) largest P with ending m, (-1,0) is sentinel
for c,m,p in seq:
i = dp.bisect_left((m+1,)) -1 # the last <= m
w = dp[i][1]+p
# remove larger ending but smaller weight
while i+1<len(dp) and dp[i+1][1]<=w:
dp.pop(i+1)
dp.add((m,w)) # same key is ok
#
print(dp[-1][1])
```
下面一題的程式其實非常簡單，只是需要一點思考，也需要使用動態的資料結構，我們把它列作習題，但給予提示。
---
##### Q-6-23. 直升機抓寶 (@@)(*)(105高中全國賽)
小智的學校在天空之城，他每天開直升機上學，現在他想要規劃一條路徑以便在從家裡到學校的路上可以抓到最多的寶貝，請你寫個程式幫助他。
我們將學校與他家之間所有的位置劃分成$N\times N$的格子，每個格子以坐標 $(x,y)$ 表示，其中 $x$ 代表水平距離，$y$ 代表高度，而小智家的坐標在$(0,0)$的位置，學校在$(N-1,N-1)$的位置，由於他的父母不准他上學途中貪玩繞路，直升機被設定成每次只能向前或向上一格，也就是說，如果從$(x,y)$到$(x+1,y)$或$(x,y+1)$，當然，他也不可以超過$x<N$且$y<N$範圍，否則會無法到達學校。
小智到學校的路途上一共有$N$隻寶貝，每隻寶貝可以補獲的範圍是某特定高度而水平座標在某連續區間的格子。明確的說，對於寶貝$P(i)$, $0\le i <N$，要捕抓到 $P(i)$，小智必須經過下列座標之一：$\{(x,y)\ |\ S(i)\le x\le T(i) \text{ and } y=i\}$，其中所有的$S(i)$與$T(i)$都已經透過抓寶雷達得到資料了。
上圖是一個N=5的例子，藍色區塊顯示可以捕抓到寶貝的地方，請注意，每一個寶貝都是在一個水平連續區間。紅線所顯示的路徑是一條合乎規定的路徑，因為他每一步都只有向右或向上，沿這一條路徑可以捕抓到四隻寶貝，是所有可能路徑中可以捕抓到寶貝數最多的。
Time limit: 5 秒
輸入格式：第一行是座標範圍的N，接下來N行，每一行有兩個整數$S(i)$與$T(i)$，依序是$i=0,1,…N-1$，其中$0\le S(i)\le T(i)<N \le 2.5e5$。
輸出：最多可能抓到的寶貝數。
範例一輸入：
5
1 3
0 1
3 4
0 0
2 3
範例一輸出：
4
範例二輸入：
2
1 1
0 0
範例二輸出：
1
---
如果我們從下往上一步一步看，令 $p[x]$ 是當時走到X座標 $x$ 能抓到的最多寶貝數量，顯然 $p[]$ 是一個非遞減陣列。那麼其實我們要做的很簡單：在高度 $i$ 時，讀取一個區間$[s,t]$，對於 $p[s]$ ~ $p[t]$，把數字增加 1；對於$x>t$，如果 $p[x]<p[x-1]$，則$p[x]=p[x-1]$，也就是做prefix maximum的動作。以下是這樣直接寫的程式，時間複雜度是$O(n^2)$，這一題的重點就是如何優化，作法就列入(困難的)習題了，給一個提示：$p[]$是一個非遞減陣列，我們不一定要存$p[]$，可以只存它上升的位置。
```python=
# Q-6-23 touch max intervals by an increasing path
# naive method, O(N^2) method
n = int(input())
p = [0]*n
for i in range(n):
s,t = [int(x) for x in input().split()]
for j in range(s,t+1):
p[j] += 1
j = t+1
while j<n and p[j] < p[j-1]:
p[j] = p[j-1]
j += 1
#
print(p[-1])
```
下面這一題不需要特殊的資料結構，但是思考比較困難。
---
##### Q-6-24. 隔離採礦 (@@@)(108全國高中賽)
外星採礦隊在烏邦圖星球已經探勘到某種礦物的礦脈，這條礦脈是一個筆直的直線，且一共有 $n$ 個可以挖礦井的地點，這些地點就稱為可開採點。所有的可開採點由1到 $n$ 依序編號，第 $i$ 個可開採點的高度為 $h(i)$ 而開採價值為 $v(i)$。
現在希望能找出某些可開採點來實際進行鑽井挖礦，因為安全因素，任兩個礦井之間必須有另外一個開採點，其高度超過這兩個礦井。身為外星採礦隊的程式設計師，你的目標是計算出最大的開採價值總和。
下圖是一個 $n =10$ 的例子，圖中各點的高度為 $y$ 軸座標，而開採價值則標註於各點旁邊。如圖所示，各點的高度依序是 $h = (2, 5, 3, 2, 4, 2, 3, 1, 4, 3)$，而開採價值則依序是 $v = (1, 8, 3, 1, 5, 1, 4, 2, 4, 2)$，也就是說 $h(1)=2, h(2)=5, …, h(10)=3$，而$v(1)=1, v(2)=8, …, v(10)=2$。在此例中，最佳的開採方式是圖中被圓圈所圈起來的四個點，所能獲得的最大開採價值總和為1+3+4+2=10。你可以看到，任兩個實際開採點之間都有一個高度更高的點。
Time limit: 5 秒
輸入格式：每筆測資的第一行是一個正整數 $n$， $n \le 1e6$，代表可開採點的數量。第二行是 $n$ 個非負整數，依序代表每一點的高度 $h(1), h(2), …, h(n)$；第三行是 $n$ 個正整數，依序代表每一點的開採價值 $v(1), v(2), …, v(n)$。每一行相鄰數字間以一空白間隔。每一點的高度不會超過1e9，價值不會超過1e5。
輸出：輸出爲一整數，代表最大的開採價值總和。每筆測資的答案不超過2e9。
範例一輸入：
10
2 5 3 2 4 2 3 1 4 3
1 8 3 1 5 1 4 2 4 2
範例一輸出：
10
範例二輸入：
5
3 3 3 3 3
5 3 2 3 4
範例二輸出：
5
---
這題有很多解法，最好的解法是$O(n)$的DP，但是轉移式比較不容易想，另外也有幾種$O(n\log(n))$的解法。
下面這一題其實是赫赫有名的經典題TSP(travelling salesperson problem)。
---
##### Q-6-25. 貨郎問題 (@@)
有一個賣貨郎要旅行 $n$ 個城市做生意並且回到他的家，由於路途遙遠，他希望走的路程總和越短越好，希望你幫他規劃最短路線。這 $n$ 個城市由 0 ~ $n-1$編號，他的家在編號 $m$ 的城市。對任意兩個城市 $i$ 與 $j$，已知兩者之間的距離是$d[i][j]$，而且繞經第三地的路程絕對不會更短。
Time limit: 4 秒
輸入格式：第一行有兩個正整數 $n$ 與 $m$。接下來 $n$ 行每行 $n$ 個非負整數是矩陣 $d[i][j]$ 的內容，順序由上而下，由左而右，$i$從 0 ~ $n-1$，$j$ 從 0 ~ $n-1$。$n \le 16$，假設$d[i][j]=d[j][i]$, $d[i][i]=0$, 且 $d[i][j] \le 100$。
輸出：最短總路程。
範例一輸入：
4 0
0 1 1 2
1 0 1 2
1 1 0 1
2 2 1 0
範例一輸出：
5
範例二輸入：
4 2
0 2 1 1
2 0 1 1
1 1 0 2
1 1 2 0
範例二輸出：
4
範例一說明：走的順序與距離 0 -> 1 -> 2 -> 3 -> 0，距離總和 1+1+1+2=5。
範例二說明：走的順序與距離 0 -> 2 -> 1 -> 3 -> 0，距離總和 1+1+1+1=4。
---
一個人要把 $n$ 個城市都走一遍再回到起點，題目中說，對任兩個城市來說，繞經第三地並不會比較近，因此單純的可以看作是一個找排列的方式，這一題的 $n$ 到 16，$16!$實在太大了，所以要找更快的方法。
這一題並不需要特殊的資料結構或演算法，所以未必是APCS不能考的範圍，我們給予提示，作為習題。因為要繞一圈，起點根本不重要，輸入資料中給起點只是唬人的把戲，我們可以假設0是起點。
以狀態轉移來想想看，有哪些狀態呢？對於兩個相同起點的不同的路徑(尚未走完)，如果它們走過的點集合一樣，最後停留的點也一樣，那麼這兩條路徑就只需要一條比較短的就可以了，例如$P=(0, 1, 3, 7, 4)$與$Q=(0, 7, 3, 1, 4)$，他們經過的點集合都是$\{0,1,3,4,7\}$而最後停留點都是 4，所以並不需要都留下來，也就是說，我們需要考慮的狀態是所有的$(S, p)$，其中 $S$ 是所有的子集合，而 $p$ 是所有可能的點，這樣的DP需要的複雜度還是指數，因為有$2^n$ 個子集合與 $n$ 個可能的點，所以狀態數是$O(n2^n)$，每一個轉移會牽涉$O(n)$前置狀態，所以時間複雜度是$O(n^2\times 2^n)$，雖然是指數形式，但比$O(n!)$要好很多。
**End of chapter 6**
Sign in with Wallet
Connect another wallet