最大子数组
这个题，初学之时，老师教我们用分治算法，分三路：在左边子数组、在右边子数组以及跨越中线，其实用动态规划已经很简单了，看状态转移方程就明白了：
[dp[i] = egin{cases}arr[i], & quad i==0\
max{dp[i-1]+arr[i], arr[i]}, & quad otherwise
end{cases}
]
def maximum_subarr(arr):
if not arr:
return None
dp = [0]*len(arr)
dp[0] = arr[0]
for i in range(1, len(arr)):
dp[i] = max(dp[i-1]+arr[i], arr[i])
return max(dp)
编辑距离
状态转移方程为：
[dp[i][j] = egin{cases}dp[i-1][j-1], & quad s1[i] == s2[j]\
min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}+1, & quad otherwise
end{cases}
]
注意边界的情况：i、j是从1开始的，0表示空字符串。
def edit_distance(s1, s2):
if len(s1) == 0:
return len(s2)
if len(s2) == 0:
return len(s1)
dp = [[0]*(len(s2) + 1) for _ in range(len(s1) + 1)]
for i in range(len(s1)+1):
for j in range(len(s2)+1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
else:
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
return dp[len(s1)][len(s2)]
最长公共子串
状态转移方程为：
[dp[i][j] = egin{cases}dp[i-1][j-1]+1, & quad s1[i] == s2[j]\
0, & quad otherwise
end{cases}
]
最终的答案是整个dp数组中的最大值。
def longest_common_substring(s1, s2):
if not s1 or not s2:
return 0
max_len = 0
dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
else:
dp[i][j] = 0
return max_len
最长公共子序列
子序列可以不是连续的，所以，状态转移方程为：
[dp[i][j] = egin{cases}dp[i-1][j-1]+1, & quad s1[i] == s2[j]\
max{dp[i-1][j], dp[i][j-1]}, & quad otherwise
end{cases}
]
def longest_common_subseq(s1, s2):
if not s1 or not s2:
return 0
m = len(s1)
n = len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] != s2[j-1]:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
else:
dp[i][j] = max(max(dp[i-1][j-1]+1, dp[i][j-1]), dp[i-1][j])
return dp[m][n]