Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit510b054

Browse files
author
shengshijun
committed
动态规划解决最长回文子序列问题
1 parent6408555 commit510b054

File tree

5 files changed

+124
-4
lines changed

5 files changed

+124
-4
lines changed

‎README.md

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -27,12 +27,14 @@ algorithm
2727
2. 使用自底向上方法实现的最大子数组
2828
3. 使用动态规划的两种方式实现的LCS（最大公共串）（下面的算法都会使用动态规划的两种方式来实现）
2929
4. 加权有向无环图中最短路径和最长路径
30+
5. 背包问题
31+
6. 最长回文子串(lps)
3032

3133
###幂乘：算法复杂度是O(lgn)
3234
##贪心算法
3335
1. 活动选择问题
34-
2.顶点作色问题
35-
3.带权活动选择问题(其实就是一个调度问题）
36+
2.带权活动选择问题(其实就是一个调度问题）
37+
3.分数背包问题
3638

3739
###斐波那契树
3840
1. 使用循环实现的算法o(n)

‎dynamic/lcs/down_up.py

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -53,10 +53,10 @@ def __lcs(list_x, list_y, end_x, end_y, __len_dict, __ele_dict):
5353
__ele_dict[(x,y)]="\\"
5454
elif__len_dict[(x-1,y)]>=__len_dict[(x,y-1)]:
5555
__len_dict[(x,y)]=__len_dict[(x-1,y)]
56-
__ele_dict[(x,y)]='|';
56+
__ele_dict[(x,y)]='|'
5757
else:
5858
__len_dict[(x,y)]=__len_dict[(x,y-1)]
59-
__ele_dict[(x,y)]='-';
59+
__ele_dict[(x,y)]='-'
6060
return__len_dict[(end_x,end_y)]
6161

6262

‎dynamic/lps/__init__.py

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
__author__='shenshijun'
4+
5+

‎dynamic/lps/down_up.py

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
__author__='shenshijun'
4+
"""
5+
使用自下而上的方法实现的最长回文序列
6+
"""
7+
8+
9+
deflps(seq):
10+
value_dict= {}
11+
seq_len=len(seq)
12+
seq_dict= {}
13+
foriinxrange(seq_len):
14+
value_dict[(i,i)]=1
15+
seq_dict[(i,i)]="/"
16+
17+
forjinxrange(seq_len):
18+
foriinreversed(xrange(j)):
19+
ifseq[i]==seq[j]:
20+
# 注意：在对角线上的对称点必须按照0算，不能按照一算
21+
value_dict[(i,j)]=value_dict.get((i+1,j-1),0)+2
22+
seq_dict[(i,j)]="/"
23+
else:
24+
value_dict[(i,j)]=max(value_dict[(i+1,j)],value_dict[(i,j-1)])
25+
seq_dict[(i,j)]='|'ifvalue_dict[(i+1,j)]>value_dict[(i,j-1)]else'-'
26+
return {
27+
"len":value_dict[(0,seq_len-1)],
28+
"char":"".join(extra_lps(seq_dict,0,seq_len-1,seq).values())}
29+
30+
31+
defextra_lps(seq,start,end,origin_list):
32+
cur_x=start
33+
cur_y=end
34+
result= {}
35+
while (cur_x,cur_y)inseq:
36+
ifseq[(cur_x,cur_y)]=='/':
37+
result[cur_x]=origin_list[cur_x]
38+
result[cur_y]=origin_list[cur_y]
39+
cur_x+=1
40+
cur_y-=1
41+
elifseq[cur_x,cur_y]=='-':
42+
cur_y-=1
43+
else:
44+
cur_x+=1
45+
returnresult
46+
47+
48+
defmain():
49+
printlps('character')
50+
51+
52+
if__name__=="__main__":
53+
main()

‎dynamic/lps/up_down.py

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
__author__='shenshijun'
4+
"""
5+
自上而下实现最长回文子序列问题，即从一个字符串中求出一个子序列，其内容是回文，而且保证长度是最长的。
6+
注意：并不要求子序列是连续的。
7+
"""
8+
__value_dict= {}
9+
__seq_dict= {}
10+
11+
12+
deflps(seq,start,end):
13+
global__value_dict
14+
global__seq_dict
15+
if (start,end)in__value_dict:
16+
return__value_dict[(start,end)]
17+
ifstart==end:
18+
result=1
19+
__seq_dict[(start,end)]="/"
20+
elifstart>end:
21+
return0
22+
elifseq[start]==seq[end]:
23+
result=lps(seq,start+1,end-1)+2
24+
__seq_dict[(start,end)]="/"
25+
else:
26+
left=lps(seq,start+1,end)
27+
right=lps(seq,start,end-1)
28+
result=max(left,right)
29+
__seq_dict[(start,end)]="-"ifright>=leftelse"|"
30+
__value_dict[(start,end)]=result
31+
returnresult
32+
33+
34+
defextra_lps(seq,start,end,origin_list):
35+
cur_x=start
36+
cur_y=end
37+
result= {}
38+
while (cur_x,cur_y)inseq:
39+
ifseq[(cur_x,cur_y)]=='/':
40+
result[cur_x]=origin_list[cur_x]
41+
result[cur_y]=origin_list[cur_y]
42+
cur_x+=1
43+
cur_y-=1
44+
elifseq[cur_x,cur_y]=='-':
45+
cur_y-=1
46+
else:
47+
cur_x+=1
48+
returnresult
49+
50+
51+
defmain():
52+
char_list="character"
53+
printlps(char_list,0,len(char_list)-1)
54+
printextra_lps(__seq_dict,0,len(char_list)-1,char_list)
55+
56+
57+
if__name__=="__main__":
58+
main()
59+
60+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp