題目連結

https://zerojudge.tw/ShowProblem?problemid=c001

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1346

參考文章

Dynamic Programming (LCS)

本題要點

LCS 跟 a133. 10066 - The Twin Towers 一樣

要動的只有輸入，其他的概念、方法，都一樣

10066 - The Twin Tower

參考解答

解一：

while True:
	try:
		s1 = input()
		s2 = input()
		# 初始化 dp
		dp = []
		s1_len, s2_len = len(s1), len(s2)
	
		# 讓dp長寬多一格 先預設0
		for _ in range(s1_len+1):
			dp.append([0 for _ in range(s2_len+1)])
	
		# LCS
		for i in range(1, s1_len+1):
			for j in range(1, s2_len+1):
				if s1[i-1] == s2[j-1]: # 從 index = 0 的位置開始比對字串
					dp[i][j] = dp[i-1][j-1] + 1 # 從 dP[1][1]的位置開始計算
				else:
					dp[i][j] = max(dp[i-1][j], dp[i][j-1])
	
		print(dp[s1_len][s2_len])
	except:
		break

回主頁