【动态规划2】最大子段和，编辑距离，括号匹配问题...

vlambda
2020-04-30

【动态规划2】最大子段和，编辑距离，括号匹配问题...

感觉不管是一些考试，还是面试，动态规划的题目都是考的最多的... 还是按照上一篇的基本思路，下面来看几个进阶一点的例子。

【别问为啥放图片，都是套路】

最大子段和【动态规划】

问题描述：对给定的一段字符比如{-9,10, 20, -30},求出它的最大连续子序列之和。显然对于本序列应该就是{10,20}，结果应该为30。

还是按照动态规划的基本套路：（1）dp[i]表示到第i个字符之前（包括第i个字符），所具有的最大子序列之和。（2）状态转移方程。现在假设dp[i-1], dp[i-2]..等等数据全部已经知道，现在要求dp[i]只有两种情况，第一种如果dp[i-1]为负数，则dp[i] = list[i],第二种如果dp[i-1]大于等于0，则dp[i] = dp[i-1] + list[i]代码如下：

if dp[i-1] < 0: dp[i] = list[i]else:  dp[i] = dp[i-1] + list[i]

(3)递归边界：dp[1] = list[0]

综上，代码如下：

def getMaxSubSeq(seq: list) -> int: dp = [0] * (len(seq) + 1) dp[1] = seq[0] for i in range(2, len(seq)+1): if dp[i-1] >= 0: dp[i] = dp[i-1] + seq[i-1] else: dp[i] = seq[i-1] return max(dp)

if __name__ == '__main__': print(getMaxSubSeq([-2,11,-4,13,-5,-2]))##########20

2.编辑距离【动态规划】

编辑距离问题是一个比较经典的动态规划问题，在生物信息中的应用就是比对算法。

问题描述：现在有序列s1：rad,s2:apple，问最少需要经过几步能够将s1变成s2。比如将上述s1变成s2最少需要5步。在s1中插入e,插入l，插入p，将d变成p，删除r（从后往前）。

还是按照动态规划的基本套路：（1）dp[i][j]表示s1中的第i个字符之前（包括第i个字符），变成s2中的前j个字符（包括j）所需要的最小编辑次数；(2)状态转移方程。假设dp[i-1][j-1]等等数据均已经知道，现在要求dp[i][j]。

if s1[i] == s2[j]:  dp[i][j] = dp[i-1][j-1]else:  dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1,dp[i-1][j-1]+1)

这里 dp[i-1][j]+1, dp[i][j-1]+1,dp[i-1][j-1]+1有点不好理解， dp[i][j -1 ]+1代表的是在s1中插入一个元素， dp[i -1 ][j]+1代表在s1中删除一个元素， dp[i -1 ][j -1 ]+ 1代表对应位置的替换元素。（ 3）初始条件。 dp[0][j]=j,dp[i][0]=i

综上，代码如下：

def getEditDistance(s1: str, s2: str): dp = [[0 for _ in range(len(s2)+1)] for __ in range(len(s1)+1)] for i in range(len(s1)+1): dp[i][0] = i for j in range(len(s2)+1): dp[0][j] = j 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] else: dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1) return dp[len(s1)][len(s2)]

if __name__ == '__main__': print(getEditDistance('rad', 'apple'))###########5

3.求括号匹配问题【栈的应用】

问题描述：现在字符串由三种括号{}，（），【】组成，比如[{()}],现在要判断该字符串中的括号是否匹配。

该问题的关键点在于左括号全部进栈，然后遇到右括号就判断是否匹配，不匹配就false。

综上，代码如下：

def isMatched(s: str) -> bool: def isExited(p: str) -> str: if p == '}': return '{' if p == ')': return '(' else: return '['
 stack = [] for i in s: if i == '(' or i == '{' or i == '[': stack.append(i) else: if len(stack) != 0 and stack.pop() == isExited(i): continue else: return False return True

if __name__ == '__main__': print(isMatched('[{(})]')) ########## False

python小技巧：列表生成式：[[0 for i in range(5)] for j in range(5)]注意：在编辑距离中插入，删除，替换，dp值都要加1，原因是这三种都算是进行了一次修改

vlambda博客
学习文章列表