- Mark
Length i | 1 | 2 | 3 | 4 |
---|---|---|---|---|
Price Pi | 15 | 20 | 33 | 36 |
Limit Li | 2 | 1 | 1 | 1 |
Example : length = 4
4 => 36
1,3 => 48
2,1,1 => 50 best
與上周的做法比較:
1,1,1,1 => 60
但此作法會超過的限制,需改良
- xian
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
0.04 | 0.06 | 0.08 | 0.02 | 0.10 | 0.12 | 0.14 | ||
0.06 | 0.06 | 0.06 | 0.06 | 0.05 | 0.05 | 0.05 | 0.05 |
Let e[i,j]
= the value of optimal solution for ,而每一個最佳解的root會有左右子樹,左右子樹也分別有它的最佳解,可以利用DP二維矩陣找出最佳解,並利用例外一個二維矩陣r[i,j]
來記錄root為多少時有最佳解。
By table of e[i,j], the cost of an optimal binary search tree is 3.12.
By table of r[i,j], the structure of an optimal binary search tree is the image below.
- LXS
Given two sequences and and set of transformation operation costs, the edit distance from to is the cost of the least expensive operation sequence that transforms to . Describe a dynamic-programming algorithm that finds the edit distance from to and prints an optimal operation sequence. Analyze the running time and space requirements of your algorithm.
Operations:
dist[i][j] 表示 轉換至 的 Edit distance
題目目標為 dist[m][n] 即 轉換至 的 Edit distance
dist[i][j] = dist[i][j-1]+cost[INSERT]
dist[i][j] = dist[i-1][j]+cost[DELETE]
dist[i][j]= min(dist[i][j-1], dist[i-1][j], dist[i-1][j-1])+cost[REPLACE]
dist[i][j] = min(dist[i][j], dist[i-2][j-2]+cost[TWIDDLE]);
Generalize:
Boundary:
當 i==0
或 j==0
即其中一者為空字串,最小 Edit distance 為 Insert/Delete 的次數。
Time complexity:
Find Distance:
Time complexity:
Space complexity:
Backtracking:
Time complexity:
Space complexity:
- songchiu
透過來存放目前為止,字串、字串共有幾個相同的數
【式子】
c[] | B | A | D | B | C | B | A |
---|---|---|---|---|---|---|---|
A | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
B | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
A | 1 | 2 | 2 | 2 | 2 | 2 | 3 |
C | 1 | 2 | 2 | 2 | 3 | 3 | 3 |
D | 1 | 2 | 3 | 3 | 3 | 3 | 3 |
B | 1 | 2 | 3 | 4 | 4 | 4 | 4 |
C | 1 | 2 | 3 | 4 | 5 | 5 | 5 |
由上表可知,LCS為《》,長度為 (順序請看綠色的字)
- chung
【題目】
An algorithm to solve the LCS problem of two strings X and Y has space complexity O(|X||Y|) typically.
LCS在計算某一格的解僅需要使用到其上方、左方或左上方格子的值,因此僅需要利用兩行的陣列(上一行與目前此行)空間即可算出答案,並將較短的字串設為index j,即可讓空間複雜度為2⋅min(|X|,|Y|)
計算需要使用到(上)、(左)或(左上)的值,LCS的計算順序是由左到右、由上到下,因此可將陣列精簡成一行,並使用額外常數空間暫存左上方的值,因此可讓空間複雜度減少為1+min(|X|,|Y|)
- yee
Let be an alphabet set, denote the blank character in , and a measure function . Where is defined as followings, for any and in , if and if ; whereas . Given and be two strings of , let and denote two new strings made by inserting some into and respectively. The similarity of and is defined by measuring the maximal value of among all possible and .
與LCS很像,只是會插入空格來增加相似度,作法差不多,只是要考慮空格能插在最前面,因此建表時多加一列跟一行表示一開始空格再來建表即可
Time :
Space :
透過建好的表(score)由最右下角回推比對左上左邊及上方的分數即可知道要於何處插入空格
最壞可能就是全部都空格(m+n),因此時間複雜度為
而空間複雜度因為要建表仍然是
- xian
因為在計算LCS的c table時,如果,則,,則 (上),,則 (左),由上面規則可知( from課本p.394 b table的code ),我們只需要考慮的點有左上、上、左
這三個點,因此我們重建LCS時只需考慮這三點,即可回推所需要的解。
因為演算法一次只會向上一格,或是向左一格,所以在考慮最差的情形下,我們會從最右下角找的最左上角(m+n步),因此時間複雜度為。