→ xling5216:這題是考lcs GOOGLE一下應該會答案喔 12/20 03:56
http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_97_01.pdf
幫我看一下有沒有錯 謝謝!!
第六題(b)
我的答案:
------------------------------------------------------
利用Dynamic Programming
遞回式:
0 if i=0 or j=0
s[i,j]= s[i-1,j-1] + c[j] if P[i] != T[j]
max{s[i-1,j] , s[i,j-1]} if P[i] = T[j]
------------------------------------------------------
Max_Subseq( T , P , c)
1. m = P.length
2. n = T.length
3. for i = 1 to m
4. s[i,0] = 0
5. label[i,0] = "↑"
6. for j = 1 to n
7. s[0,j] = 0
8. label[0,j] = "←"
9. for i = 1 to m
10. for j = 1 to n
11. if P[i] == T[j]
12. s[i,j] = s[i-1,j-1] + c[j]
13. label[i,j] = "↖"
14. else if s[i,j-1] >= s[i-1,j]
15. s[i,j] = s[i,j-1]
16. label[i,j] = "↑"
17. else
18. s[i,j] = s[i-1,j]
19. label[i,j] = "←"
--------------------------------------------------------
s[i,j]為最大值
label[i,j]為路線
時間複雜度 O(m*n)
以上，不知道想法對不對...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.175.134.213
※ 編輯: AM101 來自: 1.175.134.213 (12/18 11:23)