https://zerojudge.tw/ShowProblem?problemid=a133
https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1007
一開始參考文章寫的
# LCS
for i in range(1, s1_len+1):
for j in range(1, s2_len+1):
if s1[i] == s2[j]: # 從 index = 1 的位置開始比對字串
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])
這樣寫會遇到一個問題，兩棟大樓的第0片磁磚不會被檢查到
有可能造成輸出小於正確答案的情況。
所以我更改為下方程式碼，改為從第0片磁磚開始檢查。
# 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])
而這樣會遇到原先 dp 表格長寬不夠造成 index out of range 的問題
最後我將 dp 表格長寬各增加一格（執行完如下圖），這樣就可以確保兩棟建築都有確實比對
"""
#1
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
dp = [ [0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1]
[0, 1, 1, 1, 1, 2, 2]
[0, 1, 1, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 3, 3, 4]
[0, 1, 2, 2, 3, 4, 4] ]
ooutput = 4
-----------------------------------------
#2
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
dp = [ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 2, 2, 2, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 2, 3, 3, 3, 3]
[0, 1, 2, 2, 3, 3, 3, 4, 4, 4]
[0, 1, 2, 3, 3, 3, 4, 4, 4, 5]
[0, 1, 2, 3, 4, 4, 4, 5, 5, 5]
[0, 1, 2, 3, 4, 4, 5, 5, 5, 6]
[0, 1, 2, 3, 4, 5, 5, 6, 6, 6] ]
output = 6
"""
我遇到的都是小問題XD，很好改