动态规划-建中首页

1、94 建中資訊科校內培訓CK5826馮俊菘Dynamic Programming方法概述在 Divide and Conquer 的時候，如果一次會分成數個子問題，很容易就會要重複計算一些子問題，這樣非常浪費時間。所以我們建一張表，把所有子問題的答案存下來，下次再碰到時，就可以直接用。這是由上而下的做法。我們也可以倒過來，由下往上做，就是先把可能遇到的子問題都處理好，再一步一步推回原本的問題。用 Dynamic Programming，最重要的是 DP 元素和遞迴式。DP 元素就是表格上每一格存的東西所代表的意義； 遞迴式就是用子問題答案建構出原問題答案的方法。通常決定了這兩樣東西，就可以很容

2、易的寫出程式。而這兩樣東西的好壞，會決定這個演算法的好壞。如果題目不只求最佳解的值是多少，還要問如何解 ，那多半需要把 DP過程中所做的選擇記錄下來，然後從最後面trace-back回去。題1生產線現在有兩條生產線，每條線有 n 個工作站，第 a 條線上的第 b 個站需要 A a,b 的時間。每一個貨物都要依序經過 n 個工作站（無論在哪條線上） ，才能出廠。從工作站 W1,x 到 W1,x+1 不需要花時間，但是從 W1,x 到 W2,x+1 需要 T1,x 的時間；同樣的，從 W2,x 到 W1,x+1 需要 T2,x 的時間。進入生產線和從生產線送出分別需要E1、E2、X1、X2 的時間

3、。給定這些時間，若想以最快的方式生產一件產品，要經過哪些工作站？DP 元素： Timea, b 表示 第 a 條生產線第 b 個站到出口所需的最短時間遞迴式： Timea, b = min Timea, b+1, Time3-a, b+1 + T a,b 題 2 Longest Common Subsequence（最長共同子序列）定義：字串 p 為字串 s 的 subsequence 若且唯若 p 的每個字元都按照順序出現在 s 中。（不一定要連續，連續的又稱為 substring）例如字串 ”abc”的 subsequence有“”、“a”、 “b”、“c”、“ab”、 “bc”、“ac”

4、、“abc”。現在給定兩字串 s、t，求一字串 p，滿足 p 同時為 s 及 t 的 subsequence，且 p 的長度最長，此時稱 p 為 s 與 t 的 LCS。例： ”bronze”和 ”crown”的 LCS 為 ”ron”。1/494 建中資訊科校內培訓CK5826馮俊菘DP 元素： lena, b 表示 s1.a 和 t1.b 的 LCS 長度遞迴式： lena, b = max lena-1, b , lena, b-1 , lena-1, b-1 + (sa = tb) 變化：如果要求 3 個字串以上的 LCS 呢 ?題 3 Longest Incresing Subseq

5、uence （最長遞增子序列）給定一數列，求此數列的一個最長的子序列，且該子序列嚴格遞增。這有很多種方法，有 O(n2) 的，也有 O(n lgn) 的。另外，也可以利用LCS 來求 LIS。例： 5, 2, 8, 7, 3, 1, 6, 4 的 LIS 為 2, 3, 4或 2,3, 6 。DP 元素： lena 表示 結束在 a 的 LIS 長度遞迴式： lena = max lenb|b a & sb sa + 1題 4矩陣相乘矩陣 Ap 1, p2 和 Bp 2, p3 相乘，需要 p1*p 2*p 3 次乘法，得到p1, p3的矩陣。若一系列的矩陣相乘，順序不同，所需乘法的數量不一樣

6、。像 1, 3*3, 5*5, 4 ，若先乘前兩項，會需要1*3*5 + 1*5*4 = 35 次乘法；若先乘後兩項，則需要3*5*4 + 1*3*4 = 72 次乘法。現在給定 n 個矩陣的大小，保證一定可乘，求最少需幾次乘法？要怎麼乘？DP 元素： ma, b 表示 從矩陣 a 乘到矩陣 b 所需的最少乘法數遞迴式： ma, b = minma, k + mk+1, b + a x*k y*b y|a = k b 題 5最大子矩陣給定一矩陣 m，求一個子矩陣其中的元素和最大。5-1 一維矩陣3最暴力的做法是 O(n )，對每個起點、終點都加一次，求最大值。2用預先累加的 pre - pro

7、cessing技巧可以做到 O(n )。最好的做法是 O(n)。DP 元素： suma 表示 結束在 a 的最大子矩陣和遞迴式： suma = max 0 , suma-1 + ma5-2 二維矩陣窮舉所有可能的起點、終點，並一一算出每個子矩陣的和，再求最大值，這個方法是 O(n6)。同樣用 pre-processing的技巧，可以變成 O(n4)。這裡的 pre-processing，是讓2/494 建中資訊科校內培訓CK5826馮俊菘ma, b 代表 1, 1 a, b 內的元素和。 a, b c, d 的子矩陣元素和就等於 mc, d mc, b-1 ma-1, d + ma-1, b-

8、1，這樣可以在 O(1)的時間得到任意子矩陣的和。如果搭配維度壓縮的技巧，可以做到O(n3)。題 6 Maximal Rectangle給一個二維的布林矩陣，求一個面積最大的子矩陣，裡面全部都是1。6-1 正方形子矩陣所求的矩陣必須是正方形，加了這個條件，好做很多。DP 元素： ma, b 表示 以 a, b 為右下角的最大非0 子矩陣邊長遞迴式： ma, b = min ma-1, b , ma, b-1 , ma-1, b-1 + 16-2 長方形子矩陣長方形有不同的長和寬，不能在每一格直接確定哪一種長方形一定比較好，也不能直接選取面積最大的。如右，若在(4, 3)的地方選了 3*3 的長

9、方形，那在 (5, 3) 處就找不到 5*2 的最大長方形。所以要把每種長寬分開來做。這裡講的是 O(n3) 的方法，還可以更快。用的是 pre-processing的技巧。 DP 元素： ma, b, c 表示 以 a, b 為右下角高為 c 的最大非 0 子矩陣的寬遞迴式： ma, b, c = min ma, b-1, c-1 , ma, b, 1 題 7 0-1 背包問題上次在講的分數背包 ，是物品可以切割的情形。這次的0-1 背包，就是指物品只能拿0 個或拿 1 個，不能切割。當然，這次不能再 greedy 了，請看反例：背包重量限制： 50編號 x123重量 W x102030價值

10、 Vx100150210如果用上次那種 greedy 的方法，會拿 1, 2 ，價值 250，剩下 20 的重量浪費掉了。然而最佳解是拿 2, 3 ，價值 360，沒有浪費重量。DP 元素： ma, b 表示 在物品 1.a 中拿取總重量 b 能得到的最大價值遞迴式： ma, b = max ma-1, b , ma-1, b-W a + V a 3/494 建中資訊科校內培訓CK5826馮俊菘題 8 非常速配 （92 北市賽）給定兩小寫字串（ 3 len 15），請依以下方式計算此兩字串的相似程度。可以在兩字串的任何位置加入空白，其中一種加入空白的方式使所得分數最大，問分數最大值為多少？相同

11、字母 1 分，不同字母-0.5 分，字母對空白-0.3 分，空白對空白分。aspire_combin_e_“aspire”和 “aspect”的最高分是 2.8 分，如左。asp_ectca_ncel“combine”和 “cancel”的最高分是 1 分，如右。題 9 賣香蕉 （ TOI2005 第二次模擬考）有一家賣香蕉的商店，跟一個蕉農簽約：每天用每公斤C 元的單價，買進與前一天相同數量的香蕉。若要再增加，需要額外付每公斤P 元的處理費；若當天沒賣完，可以選擇退貨，需要花每公斤Q 元的處理費，也可以選擇送給員工帶回家 .。每天的數量= 當天本來買進的量+ 額外增加的量- 退回的量現在給你N 天的銷售數量 (N=30) 以及 C、P、Q，求最小的進貨成本。Dynamic Programming 這部分的題目很多，類型也很雜，難度變化很大，這邊只舉出幾個較簡單的例子。有時候一個題目就有很多種 DP 的方法，每種方法所需的時間和空間複雜度也不一樣。這需要多練習，才能靈活運用。還有，實作也很重要，大家要把這幾次講的題目好好寫一遍，有問題記得要問。特別強調一點，想要真的學好這門學問，請當一個獵食者 ，而不是受食者。連續三個禮拜，講